# Graph Theory

1. Jul 2, 2008

### SNOOTCHIEBOOCHEE

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. Jul 2, 2008

any takers?

3. Jul 3, 2008

### HallsofIvy

Staff Emeritus
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
4. Jul 3, 2008

### SNOOTCHIEBOOCHEE

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