6
$\begingroup$

Any help would be appreciated.

If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

  • 0
    The result isn’t actually true for graphs in general; it is true, however, for simple graphs, i.e., graphs without loops or multiple edges, and I expect that those are the ones that you meant.2012-12-05
  • 0
    Yes I'm sorry I forgot to include that the graph is assumed to be simple and connected.2012-12-05
  • 0
    The assumption of connectedness isn't required; see Brian's answer, which does without it.2013-05-06

2 Answers 2