1. Graph Representation:
- Represent the chess tournament as a graph G where each vertex represents a contestant.
- Draw an edge between two vertices if the corresponding contestants did not play each other.
2. Properties of the Graph:
- Given that if any two contestants A and B did not play each other, there exist exactly two other contestants C and D who played against both A and B. This implies that for every edge AB in G, there is a pair of vertices C and D such that AC,AD,BC, and BD are not edges in G. We call such pairs of edges conjugates.
- Additionally, no four contestants played exactly five games among them, which implies that there are no subgraphs isomorphic to K4 minus one edge.
3. Maximal Degree Argument:
- Consider a vertex X with maximal degree in G.
- Let U be a neighbor of X and Z be an endpoint of the conjugate edge of XU.
- For each neighbor Y of X, either ZY is an edge, or Z is the endpoint of the conjugate edge of XY. This implies that Z has at least as many neighbors as X, so Z also has maximal degree.
4. Breadth-First Search (BFS) Argument:
- Using BFS, we can show that every vertex in the graph has the same degree.
- Start from a vertex with maximal degree and explore its neighbors. By the previous argument, all these neighbors must also have maximal degree.
- Continue this process iteratively. Since the graph is connected, every vertex will be reached, and each will be shown to have the same degree.
5. Conclusion:
- Since every vertex in the graph has the same degree, it follows that every contestant played the same number of games.
■