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?

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

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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