Solution Found!
Suppose G is a connected graph with N - 2 even vertices and two odd vertices. Let k
Chapter 5, Problem 71(choose chapter or problem)
Suppose G is a connected graph with N - 2 even vertices and two odd vertices. Let k denote the number of bridges in G. Find all the possible values of k. Explain your answer
Questions & Answers
QUESTION:
Suppose G is a connected graph with N - 2 even vertices and two odd vertices. Let k denote the number of bridges in G. Find all the possible values of k. Explain your answer
ANSWER:Step 1 of 3
We claim that .
We already saw examples of graphs that have an Euler path but have no bridges. Now we have the recursive analysis of the graphs:
1. Assume that we have a bridge connecting two odd vertices, if we remove it, we are left with two graphs with only even vertices. If we apply the previous exercise then we know that there is no more possible bridges.