1. Limited time only! Sign up for a free 30min personal 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!

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


    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