We were conducting a tournament where we had 5 teams named- A,B,C,D,E. And in the first round every team played with every other team. So there were 10 matches. But these matches happened during rainy days, So we wanted to keep things simple and the matches stopped due to rain were declared a draw. Now the results of first round are as shown in the graph:![enter image description here](https://cdn.statically.io/img/i.sstatic.net/vWuDANo7.png)
Now from the given results we derived two properties :
Property 1:
The two teams X, Y are related if X dominates Y (i.e., X
defeats Y, or X defeats a team Z which defeats Y) or Y dominates
X. For example, A and C are related because A dominates C.
Similarly, E and D are related because D defeats E. We found
that, in this outcome of Round 1, any two teams are related. That
is, X and Y are related for every pair X, Y of the teams. So this property is called 1.
Property 2:
Consider the match between A and B. As we know, A defeated B.
Assume that the match ended up in a draw. Then, the arc from A
to B disappears from the result graph. Now, does Property 1 hold
true?
Answer will be No.
Because, B and E are not related. Moreover, A and C
are not related. That is, there exist two disjoint pairs of teams
such that the two teams in each pair are not related. SheWe notes
that this is true for every non-drawn match. For example, if the
match between B and C ended up in a draw, then A and C are not
related and B and D are not related.
In a result satisfying property 1, a non-drawn match is crucial if when we assume that the match is instead a drawn match, then there will
exist two disjoint pairs of teams such that the teams in each pair
are not related. We say that results satisfy Property 2 if every
non-drawn match is crucial.
Now we have conducted this tournament for the coming year. Here the tournament will witness 9 teams, instead of 5 teams. Here the round 1 is planned as usual :every team will play with every other team exactly once.
Is there a possibility that the results of Round 1 will be similar to that in the current year? To be more precise: Is there a possibility that
the result graph will satisfy Property 1 and Property 2? In other
words, is there a possibility of result in which the teams in every
pair (of teams) are related and every non-drawn match is crucial?
The answer is yes!
Here our task is to come with such a graph on 9 vertices which satisfy both property 1 and property 2.