# Show that there are always two teams who played exactly the same number of games.

So i was given this question. There are 11 teams in a league. Each team can play against the other team only once. Show that there are always two teams who played exactly the same number of games.

My attempted solution. (based it off an example that was different but also slightly similar)

In a league with two divisions of 11 teams each there is no schedule with each team playing a game with each team in each division. In the language of graph theory, the scheduled games can be viewed as edges with 11 vertices. We are asking for a graph that is regular of degree 11, but we are also asking for the subgraph induced by the 11 teams in one division to be regular of degree 1. Since 1 and 11 are both odd, this is impossible, because every graph has an even number of vertices of odd degree.

We are working on graph theory but I have an assumption that this can be done by pigeon hole principle. I'm slightly confused on how to go about the graph theory method

• Hmmm, there is a lot of confusing language in your solution. Some examples are 1) "In a league with two divisions of 11 teams": why do you think there are 22 teams in a league? 2) "edges with 22 vertices": no, an edge has 2 vertices, you probably mean "edges on a graph with 22 vertices". 3) "regular of degree 11": not true, you were probably misled by "only once", which means "$\le 1$", not "$= 1$". – Erick Wong Mar 22 '16 at 16:04

The possible numbers of opponents is $0,1,2,3,4,...,10$. Can the eleven numbers all be different?
• @Donald First, let $m_1,\ldots,m_{11}$ be the list of the number of games played by each team. Note that it is impossible that 0 and 10 are both numbers in the list (because that would mean that there is a team that does not play, and another team that play against everybody, but both things cannot happen at the same time!). So, we have two cases depending on whether 10 appears on the list or not, but in any of the cases we have that $m_1,\ldots,m_{11}$ is a list of 11 numbers (pigeons) each of which can take one of 10 values (holes). – Darío G Mar 22 '16 at 21:39