1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory

  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
    Staff Emeritus
    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: 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Graph Theory
  1. Graph Theory (Replies: 5)

  2. Graph theory (Replies: 0)

  3. Graph Theory (Replies: 2)

  4. Graph Theory (Replies: 0)

  5. Graph Theory (Replies: 4)

Loading...