7
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh May 22 '12 at 17:57
  • $\begingroup$ I don't see how using the pigeon whole principle differs from using that identity. $\endgroup$ – Raphael May 22 '12 at 18:01
  • $\begingroup$ such a sparse graph must be a tree, right? $\endgroup$ – Strin May 23 '12 at 5:13
  • $\begingroup$ Yes it is a tree $\endgroup$ – Saurabh May 23 '12 at 7:00
  • 1
    $\begingroup$ @SaurabhHota: That insight can also be used for a proof. $\endgroup$ – Raphael May 23 '12 at 7:06
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.