0
$\begingroup$

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction?

Base Case:

$P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the 2 vertices. So both vertices have degree 1, both are leaves, so $P(1)$ is true.

Induction Hypothesis:

Assume $P(k)$ is true for some fixed $k$, i.e., the tree on $k$ vertices has at least 2 leaves.

Induction step:

Show $P(k) \implies P(k + 1)$.

  • The tree on $k+1$ vertices is obtained by adding a vertex to the tree with $k$ vertices
  • Since trees are connected, we must add an edge connecting the new vertex to one of the existing vertices in the tree.
  • Trees are acyclic, so we add an edge from any existing vertex that does not create a cycle
  • The new vertex now has degree 1

Hence, using induction, $P(n)$ is true.

$\endgroup$
  • $\begingroup$ Trees must be acyclic and connected. By drawing an edge between one of the vertices that already exists and the vertex that is being added, we are fulfilling that requirement. Then, we look at the 2 cases where we can connect the new vertex to an existing vertex without it resulting in a cycle being formed. Hence, we can form a tree on k + 1 vertices by adding a vertex to a tree with k vertices. $\endgroup$ – Nishant Roy Apr 30 '16 at 23:50
  • $\begingroup$ Unfortunately, my professor doesn't see it that way and insists on using induction. $\endgroup$ – Nishant Roy May 1 '16 at 0:21
3
$\begingroup$

I would first prove that every tree has at least one leaf.

Added: You have in fact tacitly assumed this in your first bullet point, when you say that every tree on $k+1$ vertices is obtained by adding a vertex to a tree with $k$ vertices. This requires that you be able to remove a vertex from a tree on $k+1$ vertices and still have a tree. This cannot be guaranteed unless the tree on $k+1$ vertices has a leaf. End addition.

HINT: If a graph has no leaves, start a walk at any vertex. Each vertex has degree $2$ or more, so you can always leave a vertex by an edge different from the one by which you reached it: there are no dead ends. There are only finitely many vertices, so ... ?

Now your induction step is much easier. You assume $P(k)$ and let $T$ be a tree with $k+1$ vertices. It has a leaf $u$. Remove the leaf and its attached edge; what’s left is a tree with $k$ vertices, so it has two leaves, say $v$ and $w$.

  • What’s the only way in which one of them could fail to be a leaf of $T$?
  • If that happens, you can still find two leaves of $T$; how?
$\endgroup$
  • $\begingroup$ @bof: I’d actually intended to do so and then forgot; thanks! $\endgroup$ – Brian M. Scott May 1 '16 at 0:13
0
$\begingroup$

This is a good start, but you should more explicitly use the induction hypothesis. Also be sure to treat both possibilities: what if the new node is connected to a node which used to be a leaf? Check that we still have at least 2 leaves.

$\endgroup$
  • $\begingroup$ Could you help me understand how I would do that? I'm terrible at proofs... $\endgroup$ – Nishant Roy Apr 30 '16 at 19:45
  • $\begingroup$ Divide your proof into 2 cases: in Case 1, the new node is added to something that wasn't a leaf. We still have all the old leaves, plus a new one, so we definitely have at least 2. Case 2, the new node is attached to an old leaf. The old leaf is no longer a leaf, but the new node is, so we still have at least 2 leaves. $\endgroup$ – Christian Gaetz Apr 30 '16 at 19:47
0
$\begingroup$

I think your base case and induction assumption are fine.

For $P(k+1)$, we can in fact ignore all the vertex additions that result in a cycle since tree do not contain cycles. So let us only consider the possible vertex additions that result in trees.

Case 1: Since $P(k)$ has at least 2 leaves, adjoining the new vertex to a node that is not a leaf would imply that $P(k+1)$ still has at least 2 leaves since the existing leaves remain unchanged. So it is quite obvious for this case. (Note that we cannot connect the new vertex to more than one node because it would result in a cycle).

Case 2: Assume that we adjoin the vertex only to a leaf. (Note: We cannot join a new vertex to a leaf and some other vertex since that would form a cycle). Now we need to show that the adjoined vertex is a leaf. This is trivial since it only has degree 1. Therefore it must be a leaf. So we removed a leaf (by adjoining the new vertex to it), but then obtained another one since the new vertex is in fact a leaf, so we still have at least 2 leaves in the tree.

Since it is true for both cases, you are done.

$\endgroup$
  • $\begingroup$ Thank you! This was really helpful $\endgroup$ – Nishant Roy Apr 30 '16 at 23:32
  • 1
    $\begingroup$ This proof is fine if you already know that every tree on $k+1$ vertices can be obtained by adding a vertex to some tree on $k$ vertices. Just how do you know that? $\endgroup$ – bof May 1 '16 at 0:02
  • $\begingroup$ You're right, we do not know this. A better method would be to consider the longest path in any tree. Then the starting and ending vertices of the path are leaves. $\endgroup$ – athul777 May 1 '16 at 0:53
0
$\begingroup$

Here is a simple proof using "complete induction" (aka "strong induction" aka "course of values induction"). Consider any integer $k\ge2.$ Assuming that every tree with at least two but fewer than $k$ vertices has at least two leaves, we prove that every tree with $k$ vertices has at least two leaves.

Let $T$ be a tree with $k$ vertices. Choose a vertex $v$ of $T$ which is not a leaf. (If every vertex is a leaf, there is nothing to prove.) The components of $T-v$ are trees $T_1,T_2,\dots,T_n.$ Since $T$ is a tree, $v$ is joined to to exactly one vertex in each $T_i.$ Since $v$ is not a leaf of $T,$ we have $n\ge2.$

We finish the proof by showing that each $T_i$ contains at least one vertex which is a leaf of $T.$ On the one hand, if $T_i$ has only one vertex, then that vertex, being joined only to $v,$ is a leaf of $T.$ On the other hand, if $T_i$ has more than one vertex, then by the inductive hypothesis the tree $T_i$ has at least two leaves; at most one of them is joined to $v,$ so at least one of them is a leaf of $T.$

$\endgroup$
0
$\begingroup$

Without Induction: Suppose it had less than two leaves.

If it has zero, then we start at an arbitrary source node. All nodes have degree $\geq 2$, hence we can take an edge to some node, take a different edge to some other node, and so forth. By pigeonhole principle, we must eventually run into a node we've already seen, hence there is a cycle.

If it has one, then we just start at that one leaf as the source.

$\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.