- #1
QuietMind
- 42
- 2
Homework Statement
In an n-player round-robin tournament, every pair of distinct players compete in a single game. Assume that every game has a winner —there are no ties. The results of such a tournament can then be represented with a tournament digraph where the vertices correspond to players and there is an edge x→y iff x beat y in their game.
(a) Explain why a tournament digraph cannot have cycles of length 1 or 2.
(b) Is the “beats” relation for a tournament graph always/sometimes/never: • asymmetric? • reflexive? • irreflexive? • transitive? Explain.
(c) Show that a tournament graph represents a total order iff there are no cycles of length 3.
Homework Equations
The Attempt at a Solution
I'm struggling with part c. I have the solutions posted below, but I don't fully understand the explanation.
"As observed in the previous part, the “beats” relation whose graph is a tournament is asymmetric and irreflexive. Since every pair of players is comparable, the relation is a total order iff it is transitive. “Beats” is transitive iff for any players x, y and z, x → y and y → z implies that x → z (and consequently that there is no edge z x). Therefore, “beats” is transitive iff there are no cycles of length 3. "
I do not understand "Since every pair of players is comparable, the relation is a total order iff it is transitive." I thought that total order simply meant that any two players have to be comparable, so A beats B or B beats A. To me, that seems to be satisfied by the fact that it is a round robin tournament. The answer seems to imply that this total order implies there's a hierarchy of who beats who. How do they get transitivity from the stipulation that it's a total order?