4
$\begingroup$

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by the inductive step.

Solution(?):

Let P(n) be the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

Base case (n=1):

P(1): (n=1, any tree with 1 vertice has 0 edges). A tree G is a connected graph with no cycles of length at least three. An edge E is a two-element subset of the set of all vertices V of G. In the base case, V contains one vertice. Thus there are zero two-element subsets of V, or zero edges, in G.

Inductive Step:

For every n>0, P(n) => P(n+1).

For P(n+1), where n>0 in G, n+1 vertices will form exactly n edges. All vertices are of degree 1, which means there is exactly one less edge than vertice (one edge per vertice, excluding the root vertice). Thus, any tree with n vertices will have exactly n-1 edges.


Assume P(n) is true. Then, we want to prove that the graph G, for P(n+1), has n edges.

G contains no cycles of length at least three. Thus, G must contain only one region, meaning that the edges in G do not form any regions. This means that G must contain at least one leaf (vertex with degree of 1).

Obtain a graph G' by removing one leaf from G. Because a leaf is a vertex of 1, by the definition of vertex degree, the leaf is connected to exactly one edge. Thus, removing the leaf will remove one vertex and one edge from G, to create G'. This means that for all n, n>=1, any tree with (n+1) vertices will have ((n+1)-1). or n, edges.

We have proven that the case base P(1) is true, and assuming that P(n) is true, we see that the statement remains true for n => n+1. Thus, the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges) is true by induction.


Assume P(n) is true. Then, we want to prove that the graph G, for P(n+1), has n edges.

G contains no cycles of length at least three. Thus, G must contain only one region, meaning that the edges in G do not form any regions. This means that G must contain at least one leaf (vertex with degree of 1).

Remove a leaf l from G to obtain a tree G′ with n vertices. Then, G' has n−1 edges, by the inductive hypothesis. The addition of l to G′ produces a graph with n+1 vertices and n edges, since l has degree 1.

P(1) is true, and for every n>0, P(n) => P(n+1). Thus, the predicate must be true.


I'm not exactly sure how to proceed for the inductive step., or if I doing it correctly. Any hints, or confirmation that I'm going in the right direction would be greatly appreciated.

$\endgroup$
1
$\begingroup$

For $P(n+1)$, you clain "all vertices are of degree $1$". That is not true in trees at all. Also, you need to prove $P(n+1)$, while you have only "proven" $P(n)$.

What you must do is assume that $P(n)$ is true, i.e. "all trees with $n$ vertices have $n-1$" edges. Then, take any tree $G$ with $n+1$ vertices and prove it has $n$ edges.

To do that, here's a Hint:

Find one vertex of $G$ that has a degree of $1$ (a "leaf") and remove it.

$\endgroup$
  • $\begingroup$ I get the general idea. Why would I remove a leaf though, to prove P(n) => P(n+1)? This involves adding a new vertex of degree 1 (leaf), and thus creates a new edge. $\endgroup$ – Charles Nov 11 '14 at 14:22
  • $\begingroup$ @goddfree Hint: Removing one leaf creates a graph with $n$ vertices. $\endgroup$ – 5xum Nov 11 '14 at 14:23
  • $\begingroup$ But I have already assumed that P(n) is true? It seems that this is trying to use the P(n+1) case to prove P(n), not the other way around. Sorry if I am not understanding correctly. $\endgroup$ – Charles Nov 11 '14 at 14:26
  • $\begingroup$ @goddfree Yes. You assumed P(n) is true and you want to prove $P(n+1)$ is true. To do that, you have to prove, for a tree with $n+1$ vertices, that it has $n$ edges. You do that by removing one leaf (first, you need to prove the leaf exists, but that's not hard), then looking at the resulting graph which has $n$ vertices, thus, the statement $P(n)$ may be useful in describing it. $\endgroup$ – 5xum Nov 11 '14 at 14:28
  • $\begingroup$ I made an edit to my original post, with my new proof. What parts, if any, are not correct? Also, you said that "...thus, the statement P(n) may be useful in describing it." I'm not exactly sure what this means, but I tried to incorporate P(n) to describe P(n+1) in the final paragraph of the proof. Could you please clarify what you meant, if I did not understand correctly? $\endgroup$ – Charles Nov 11 '14 at 14:53
0
$\begingroup$

We proceed by induction on $n$. When $n=1$ there exists only only tree, namely $K_1$, which has $0$ edges. Assume the result is true for every tree of order $n-1$ and size $n-2$. Let $T$ be a tree of order $n$ and size $m$. We know that every tree has at least two leaves. Let $v$ be a leaf. We also know that $T-v$ is a tree of order $n-1$ and by the induction hypothesis $T-v$ has size $n-2$. Thus $m=(n-2)+1=n-1$ and we can conclude that if $T$ is a tree of order $n$ and size $m$, then $m=n-1$.

$\endgroup$
0
$\begingroup$

Using structural induction,

P(1) holds as a tree with 1 node has 0 edges.

Inductive hypothesis: Assume P(n) holds i.e., a tree with n nodes has n-1 edges.

To prove: P(n+1) i.e, a tree with n+1 nodes has n edges.

Now consider a tree T of n nodes. Let us try to add a new node to T to make a new tree T'.

In doing so, you can add exactly one edge from any one of the existing nodes in the tree T to the new node - because, if you added more than one edge to the new node (say from another existing node in the tree), then you would introduce a cycle - and it wouldn't be a tree anymore by definition (A tree is a connected graph with no cycles).

As a result, a our new tree T' of n+1 nodes has n-1+1 (=n) edges. This proves P(n+1).

As a result, we have P(1) and P(n) -> P(n+1) - which completes our proof for P(k).

$\endgroup$
0
$\begingroup$

BASE CASE: n = 1; vertices|V| = 1, edges|E| = (|V| - 1) = 0

set n = |V|

INDUCTIVE STEP: Assume true for n = k, k >= 1.

|E| = (k - 1) == k = (|E| + 1)

Then, for n = (k + 1)

(k + 1) = |E| + 1, |E| = ((k + 1) - 1)

(k + 1) = ((k + 1) - 1) + 1

(k + 1) = (k + 1)

True

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