Graph Theory proof via induction

[SNOOTCHIEBOOCHEE]

Homework Statement

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

The Attempt at a Solution

Ok I am 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.

 

[SNOOTCHIEBOOCHEE]

any takers?

 

[HallsofIvy]

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.

 

[SNOOTCHIEBOOCHEE]

wow it took me a few read overs but then i finally got it, and it blew my mind.