An Interesting Proof

2019-3-5 created by AD1024
Graph Theory

Theorem: for all undirected graph with more than one vertice $G$, there must be at least one pair of vertice $u$ and $v$ ($u, v \in G$) such that $\deg(u) = \deg(v)$.

Proof. To show that any undirected graph satisfy the theorem, we can destruct the graph into two categories: connected and disconnected.

  1. For a connected graph, suppose there are $n$ vertice ($n \gt 1$). According to the property of an undirected graph, for each vertex, the maximum degree is $n-1$. Thus the problem becomes: putting $n$ vertice into $n-1$ boxes numbered from $1$ to $n-1$, and the number on box denotes the degree of vertice in it. It is apparent that there must be at least one box containing two vertice, and thus there must be at least two vertice having the same degree in any connected undirected graph.

  2. For a disconnected graph, we can apply the proof above to each subgraph, and we can obtain the same result for the graph constituted by all subgraphs.