So I know this is true, but I have no idea how to formally state that this is true:

Prove that an undirected, connected graph with two or more nodes(vertices) contains two nodes that have equal degree.

So I know that connected means that each node has at least 1 degree and undirected means that if a node has 1 degree, the node it connects to has at least 1 degree. So in my mind I know that if there are 2 nodes, they each have 1 degree. If there are 4 nodes there the max degree is 3, which is one node connecting to all other nodes. Thus the remaining 3 nodes have to have a degree >= 1 (due to definition of connected) and <= 3, since there are only 3 other nodes it can connect to. So no matter what degree the remaining nodes have it will either be 3,3,3; 3,2,1; 2,2,1; etc there will always be 2 nodes with the same degree. and so on for more nodes. But I have no idea how to state this formally. Any help?

  • $\begingroup$ Try assuming the graph has no two vertices with the same degree, and writing the degree sequence of the vertices (the list of degrees in non-decreasing order). Keep in mind that there are $n$ vertices and the maximum degree is $n - 1$. $\endgroup$ – Manuel Lafond Feb 2 '15 at 18:05

HINT: Use the pigeonhole principle. If $G$ has $n$ nodes, you’ve already observed that the smallest and largest possible degrees of a node of $G$ are $1$ and $n-1$, so the set of possible degrees is $D=\{1,2,\ldots,n-1\}$. How many different numbers are in $D$? How many nodes does $G$ have?

  • 1
    $\begingroup$ Why is the smallest possible degree one? You can have a node with a degree of zero. $\endgroup$ – Danny Dan Sep 1 '17 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.