Show that any simple graph has two vertices with the same degree. Let \( G \) be a simple graph of order ≥ 2. Suppose \( G \) is order 2, then \( G \) has either zero or one edge, hence \( G, \bar G \) each have two vertices with the same degree. Suppose \( G \) is order > 2, and that \( G \) is complete. Then every vertex in \( G, \bar G \) has the same degree so at least two of them do in each case. Suppose \( G \) is incomplete, then \( \bar G \) has at least one edge not in \( G \). Suppose \( \bar G \) has a single edge, then it contains two vertices with degree 1 and \( G \) has two vertices with degree one less than every other vertex. Hence any simple graph with order ≥ 2 has at least two vertices with the same degree.
