Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Low-degree nodes in sparse graphs

, ,
Problem Detail:

Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one.

I have tried to solve this problem by using the property $\sum_{v \in V} \operatorname{deg}(v) = 2|E|$. Can this problem be solved by using pigeon hole principle?

#### Answered By : Raphael

Yes, it can.

You have $n-1$ edges, which means $2n-2$ holes for node-pigeons. If every node is supposed to have degree two (or more), we have to place (at least) two pigeons for each node, that makes a total of $2n$ pigeons.

By said principle, (at least) two pigeons do not find a solitary hole, which means (at least) one node is isolated or (at least) two nodes have only one edge. As no node is isolated by assumption, you have (at least) two nodes with degree one.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1998

3.2K people like this

#### Post a Comment

Let us know your responses and feedback