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:
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. We 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.
Hints
Hint 1: The number of non-drawn matches is 15.
Hint 2: All graphs on 9 vertices can be found here
How to verify your answer?
Step 1: Create a text file containing the adjacencies of the answer graph. The first line of the file must contain two integers separated by a white space. The first integer is the number of vertices and the second integer is the number of edges. The rest of the lines must be the edges, one edge per line. For example, to denote an edge from A to B, write "A B" (without quotes) in one line. Please find here an example . It describes the directed cycle on 9 vertices.
Step 2: Download this python program. You require Python 3 to run this program.
Step 3: Run "python dpl.py <answer-file>", where <answer-file> is the text file that you created in Step 1. You can run "python dpl.py c9.txt" to see that it violates Property 1. Please make sure that you provide a connected graph for verification (disconnected graphs do not satisfy Property 1). If your answer is correct, you get an output "CORRECT".
