10 Replies - 1913 Views - Last Post: 05 August 2013 - 05:09 PM

#1 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 12:33 PM

Theorem: If T is any rooted tree with n nodes and e edges, then e = n - 1.

My Base Case would be: If T is a one-node tree, then e = 0 and n = 1 so e = n - 1 is true.

Inductive Step: I should assume my IH which is the theorem itself, but how would I "write" it out? I cant seem to guide myself here.
Is This A Good Question/Topic? 0
  • +

Replies To: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12335
  • View blog
  • Posts: 45,442
  • Joined: 27-December 08

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 01:23 PM

Which variable are you using for induction- number of edges or number of vertices? If you are doing edges, then you assume the theorem holds from e = 0 up to some arbitrary integer k. Then you prove true for the k+1 case.

Alternatively, you could prove this directly using Euler's formula: V - E + F = 1 + C. Since a tree is connected, C = 1. Since a Tree is acyclic, F = 1. Thus, V - E = 1, which can be rearranged to show that E = V - 1.
Was This Post Helpful? 1
  • +
  • -

#3 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 04:47 PM

Quote

I should assume my IH which is the theorem itself, but how would I "write" it out? I cant seem to guide myself here.


Wording is important with graph theory. You must use strong induction. Your base case is correct and as mac said, you will be performing the induction on n (which I think is a bit easier than doing it on e). Your inductive hypothesis must say "assume for all trees with k or less nodes, the theorem is true." Then you must word the rest of your proof in a way to show that the theorem is true for all trees with k+1 nodes based on your assumption in the IH.

If alternatively you say "assume the theorem is true for a tree T with k nodes" and then show that it is true for any graph produced from T with k+1 nodes, then we can simply ask "What about some other tree with k nodes". In this case you really haven't shown that the theorem holds for all graphs, only some.
Was This Post Helpful? 2
  • +
  • -

#4 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 06:39 PM

Thanks!
I am looking at my professor's solution here (last slide), and
I dont get U1, U2, U3,....,Uk. How is he breaking the tree T into more different trees? Does it look like the image below?
Image

What variable is he performing the induction?

In the sentence "T has all the nodes and edges from all the subtrees, plus one new node (its
root) and k new edges (one from its root to each of the existing roots)." What new node is he referring to? Does it look like the image below?

Image 2
Was This Post Helpful? 0
  • +
  • -

#5 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 08:19 PM

View Postmacosxnerd101, on 04 August 2013 - 03:23 PM, said:

Alternatively, you could prove this directly using Euler's formula: V - E + F = 1 + C. Since a tree is connected, C = 1. Since a Tree is acyclic, F = 1. Thus, V - E = 1, which can be rearranged to show that E = V - 1.


I haven't studied that yet in detailed. It will be covered in my upcoming readings.
right now, Induction proofs are kicking my a**. The minute I think I get it, next question
ruins it. :stupid:/>
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12335
  • View blog
  • Posts: 45,442
  • Joined: 27-December 08

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 04 August 2013 - 09:09 PM

Quote

In the sentence "T has all the nodes and edges from all the subtrees, plus one new node (its
root) and k new edges (one from its root to each of the existing roots)." What new node is he referring to? Does it look like the image below?

Consider the subtrees all in a forest initially. So you have T1, T2, T3, ..., Tn. Now add an additional vertex, which can be thought of as the root. This vertex's children are the roots of T1, T2, T3, ..., Tn. That's where the strong induction comes in.

Quote

What variable is he performing the induction?

The vertices- so n.

I cannot see your images, so I cannot answer your questions regarding those.

Quote

Induction proofs are kicking my a**. The minute I think I get it, next question

Induction is trickier with graph theory than something like number theory. Have you checked out a proof of correctness of Prim's or Kruskal's MST algorithm? The induction steps in the minimality portions of the proofs are not easy.
Was This Post Helpful? 1
  • +
  • -

#7 deprosun   User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 307
  • Joined: 16-November 10

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 05 August 2013 - 07:22 AM

Sorry, my images must have timed out.

First Image is this: Image

Second Image is this: Image 2

So T is just a graph/forest, not a tree? It consists of connected components/trees?
In the theorem, it says any "T is any rooted tree"..why?

He says " Let T be made by the second rule from U1, U2,..., Uk". Why is he changing a tree into a forest?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12335
  • View blog
  • Posts: 45,442
  • Joined: 27-December 08

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 05 August 2013 - 08:19 AM

The second image describes the induction step perfectly.

Quote

So T is just a graph/forest, not a tree? It consists of connected components/trees?
In the theorem, it says any "T is any rooted tree"..why?

T is a tree. All trees Ti up to some integer k satisfy the theorem by the inductive hypothesis. The inductive step takes a subset of those trees and connects them by a new root. Thus, strong induction.
Was This Post Helpful? 1
  • +
  • -

#9 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 05 August 2013 - 02:39 PM

I feel some of your confusion stems from the fact that your professor is using a slightly different type of induction. His proof does not actually run over the number of nodes or edges. Rather, it runs over recursive definitions. The induction step basically says "If the theorem applies to a set of subtrees, I can connect these trees to a common root and the theorem still applies". Since all trees are either the base case or produced by connecting set of rooted trees to a common root, the theorem recursively applies.

There are often many ways you can use induction to prove something. Ignore your professor's proof for the moment. How would you go about it? I think you can make a proof very similar to the sample I showed where all numbers are primes or products of primes.
Was This Post Helpful? 1
  • +
  • -

#10 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12335
  • View blog
  • Posts: 45,442
  • Joined: 27-December 08

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 05 August 2013 - 02:50 PM

The form of induction is also relaxed often times for graph theory proofs. A lot of times the phrase "by induction ..." is used, rather than the stricter form you find being emphasized in introductory proof writing classes.

Quote

His proof does not actually run over the number of nodes or edges. Rather, it runs over recursive definitions. The induction step basically says "If the theorem applies to a set of subtrees, I can connect these trees to a common root and the theorem still applies". Since all trees are either the base case or produced by connecting set of rooted trees to a common root, the theorem recursively applies.

I would sort-of disagree. It does run over the number of vertices, but it does it in a relaxed manner. It's not so formal.
Was This Post Helpful? 1
  • +
  • -

#11 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: If T is any rooted tree with n nodes and e edges, then e = n - 1.Proof

Posted 05 August 2013 - 05:09 PM

Quote

I would sort-of disagree. It does run over the number of vertices, but it does it in a relaxed manner. It's not so formal.


I agree this method is a little more relaxed. When deprosun asked which variable he is performing the induction over, I think he was asking which variable fits into k for the typical p(k)->p(k+1) or in strong induction p(base)..p(k)->p(k+1) inductive step. For the professor's technique, such templates do not apply. Though there are similarities between the professors method and how it might look using induction techniques we have covered previously, there are subtle differences. The professor's proof does not put any emphasis on the relationship between the number of nodes in the resulting tree and the subtrees. In fact, all the algebra does is introduce a new variable to represent the number of subtrees. Instead all he is doing is showing that the theorem applies to the base case, and that property is maintained when the recursive definition is performed. Since this recursive definition of a tree produces all possible trees, then it follows that the theorem applies to all trees. The Professor's induction is done on the recursive step.
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1