A graph can be decomposed into connected components. Among the connected components, there exist one with maximum size. Suppose the connected component is K with |K| node. Assume K has more than 1 node, since K is connected, the degrees of the nodes in K must be at least 1 and at most |K|-1, but there are |K| nodes, by the pigeonhole principle, there must be two nodes with the same degree.
On the other hand, if the maximum sized connected component has only 1 node, it must be the case that all nodes are not connected, pick any two nodes they will have the same degree = 0.
Q.E.D.
Aside 1: Graph theory is a great fun of it own - if I find good graph theory problem I will post it here.
Aside 2: It is a pleasure to type Q.E.D. I mean it!
No comments :
Post a Comment