(adsbygoogle = window.adsbygoogle || []).push({}); 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph Theory proof via induction

**Physics Forums | Science Articles, Homework Help, Discussion**