Thread: Graph Theory Problem

Prove that every simple graph with at least two vertices has two vertices with the same degree. Is the conclusion true for loopless graphs in general?

Please help... Thanks!

We will prove a stronger claim : every non-trivial connected component of a simple graph has two vertices of the same degree.

Let the number of vertices in the component be n. The degree of any vertex within the component has to be at least 1 and at most n-1. Since the number of vertices is 1 more than the number of assignable degrees, by the pigeon hole principle there are at least two vertices that have the same degree.

The original result easily follows from this, as any graph with at least two vertices that does not have more than one isolated vertex, will have at least one non trivial connected component.

The result is not true for loopless graphs in general. Consider G = { V={1, 2, 3}, E={(1,3), (2,3), (2,3)} }.