Graph Theory proof via induction

In summary, the conversation discusses proving by induction that the graph of any triangulation of a polygon will have at least 2 vertices of degree 2. The conversation also includes a hint to split the triangulation graph into 2 graphs at some chord. The solution involves assuming the statement is true for n vertices and then proving it for n+1 vertices by drawing a chord between two "almost adjacent" vertices.
  • #1
SNOOTCHIEBOOCHEE
145
0

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.
 
Physics news on Phys.org
  • #2
any takers?
 
  • #3
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:
  • #4
wow it took me a few read overs but then i finally got it, and it blew my mind.
 

1. What is graph theory proof via induction?

Graph theory proof via induction is a method used to prove statements about graphs by using mathematical induction. It involves breaking down a larger graph into smaller subgraphs and proving that the statement holds for each subgraph, thus proving it for the entire graph.

2. What type of statements can be proven using graph theory proof via induction?

Graph theory proof via induction can be used to prove statements about graphs such as the existence of a certain path or cycle, the number of vertices or edges in a graph, and the connectivity or planarity of a graph.

3. How does graph theory proof via induction work?

Graph theory proof via induction follows the same basic steps as mathematical induction. First, the statement is proved for a base case, usually a small graph. Then, the induction hypothesis is assumed for a larger graph, and the statement is proved for that larger graph. Finally, the induction step is used to show that if the statement holds for a larger graph, it also holds for an even larger graph.

4. What are the advantages of using graph theory proof via induction?

Graph theory proof via induction is a powerful tool in proving statements about graphs because it allows for the breaking down of a complex graph into smaller, more manageable subgraphs. It also provides a clear and logical structure for proving statements.

5. What are the limitations of graph theory proof via induction?

While graph theory proof via induction can be a useful tool, it is not suitable for all types of statements about graphs. Some statements may require other methods of proof, such as contradiction or direct proof. Additionally, graph theory proof via induction may be more complex and time-consuming for larger graphs.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
338
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
870
  • Calculus and Beyond Homework Help
Replies
2
Views
990
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Calculus and Beyond Homework Help
Replies
4
Views
987
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Back
Top