# Low-degree nodes in sparse graphs

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?

• Try proving the stronger result where the number of edges is just less than $n$ (not necessarily $n-1$). Use induction on $n$. You can assume that the graph is connected without loss of generality (why?). When you figure out the proof post it as an answer below. – Kaveh May 22 '12 at 17:57
• I don't see how using the pigeon whole principle differs from using that identity. – Raphael May 22 '12 at 18:01
• such a sparse graph must be a tree, right? – Strin May 23 '12 at 5:13
• Yes it is a tree – Saurabh May 23 '12 at 7:00
• @SaurabhHota: That insight can also be used for a proof. – Raphael May 23 '12 at 7:06

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.
Since the number of edges is $n-1$, the graph is a tree. Take a starting vertex $v$ in $V(G)$. Now start walking in any direction, and keep walking, without repeating a vertex. Since $G$ is finite, and does not contain a cycle, this process will eventually stop in a vertex $u$ of degree 1. If $v$ also had degree 1, we are done. If not, start a new walk in some other direction out of $v$. This walk also ends in a vertex of degree 1.