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)

Get Unlimited 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

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.

Add to cart


Study Tools You Might Need

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back