Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory proof via induction

  1. Jul 2, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove by induction that the graph of any triangulation of a polygon will have at least 2 vertices of degree 2

    Hint: Split the triangulation graph into 2 triangulation graphs at some chord e


    3. The attempt at a solution

    Ok im pretty terrible at induction proofs, so bare with me.

    This is trivial for the case when we only have a triangle.

    Suppose this is true for n vertices. then we want to show that it is true for n+1 vertices.

    Basically i have no clue how to do this problem.

    My guess is that we have to make e the smallest triangle possible, but that only proves that there is one edge of degree 2.

    Any help is appreciated.
     
  2. jcsd
  3. Jul 2, 2008 #2
    any takers?
     
  4. Jul 3, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    First I absolutely refuse to "bare" with you! I don't know you that well.

    Assume that the graph of any triangulation of any polygon with k sides has at least two vertices of degree 2. Now look at a polygon with k+1 sides.drawing a chord between two "almost adjacent" vertices (i.e. they have exactly one other vertex between them) divides the polygon into a triangle and a polygon with k sides.
     
    Last edited by a moderator: Jul 3, 2008
  5. Jul 3, 2008 #4
    wow it took me a few read overs but then i finally got it, and it blew my mind.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook