1
$\begingroup$

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

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".

$\endgroup$

2 Answers 2

4
+50
$\begingroup$

Graph which has 15 edges (non-drawn matches)

enter image description here

This gives the output "CORRECT" when fed to the Python script.

9 15
A B
B C
C D
D E
E F
F G
G H
H I
I A
E A
F I
I C
H D
B G
C F

Method of solving

1. Start with a nonagon. After this step, each node is related to 4 other nodes.
2. Make a triangle using nodes C, F, I. After this step, these nodes are related to every other node - satisfying Property 1.
3. Observe that there is a nice symmetry to be obtained with the last 3 edges and follow the axiom: "Math has a tendency to reward you if you respect its symmetries!" (Essence of Calculus, Chapter 1 - Grant Sanderson)

$\endgroup$
6
$\begingroup$

Here is a very symmetric graph:

enter image description here

Property 1:

The edges allow you to move forward one or two steps around the ring of nodes. Any two nodes are at most 4 apart, so are connected in at most two steps, and therefore related.

Property 2:

If edge AB is removed, then A and B are no longer related.
If edge AC is removed, then A and E are no longer related.
By symmetry, all edges are necessary.

$\endgroup$
2
  • $\begingroup$ Here is the Hint which my classmates gave: Hint 1-> The number of non drawn matches is 15. Hint 2-> All graphs on 9 vertices can be found here $\endgroup$ Commented May 12 at 6:44
  • 3
    $\begingroup$ Regardless of the hint, this answer satisfies both properties. $\endgroup$
    – Dr Xorile
    Commented May 16 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.