Question

Let G be a simple planar graph with fewer than 12 vertices. a) Prove that m...

Let G be a simple planar graph with fewer than 12 vertices.
a) Prove that m <=3n-6; b) Prove that G has a vertex of degree <=4.

Solution: (a) simple --> bdy >=3. So 3m - 3n + 6 = 3f <= sum(bdy) = 2m --> m - 3n + 6 <=0 --> m <= 3n - 6.

So for part a, how to get bdy >=3 and 2m? I need a detailed explanation

b) Assume all deg >= 5 --> 5n <= sum(deg) = 2m <= 3(3n-6) = 6n - 12 --> 5n <= 6n - 12 or 12 <= n. But n < 12. This contradiction proves that there is a vertex of deg <=4.
I need a detailed explanation for part b

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Use proof by induction to prove that every connected planar graph with less than 12 vertices...
Use proof by induction to prove that every connected planar graph with less than 12 vertices has a vertex of degree at most 4.
Let G be a simple graph with at least two vertices. Prove that there are two...
Let G be a simple graph with at least two vertices. Prove that there are two distinct vertices x, y of G such that deg(x)= deg(y).
Let G be a simple graph in which all vertices have degree four. Prove that it...
Let G be a simple graph in which all vertices have degree four. Prove that it is possible to color the edges of G orange or blue so that each vertex is adjacent to two orange edges and two blue edges. Hint: The graph G has a closed Eulerian walk. Walk along it and color the edges alternately orange and blue.
Let G be a connected simple graph with n vertices and m edges. Prove that G...
Let G be a connected simple graph with n vertices and m edges. Prove that G contains at least m−n+ 1 different subgraphs which are polygons (=circuits). Note: Different polygons can have edges in common. For instance, a square with a diagonal edge has three different polygons (the square and two different triangles) even though every pair of polygons have at least one edge in common.
30. a) Show if G is a connected planar simple graph with v vertices and e...
30. a) Show if G is a connected planar simple graph with v vertices and e edges with v ≥ 3 then e ≤ 3v−6. b) Further show if G has no circuits of length 3 then e ≤ 2v−4.
Let G be a connected planar graph with 3 or more vertices which is drawn in...
Let G be a connected planar graph with 3 or more vertices which is drawn in the plane. Let ν, ε, and f be as usual. a) Use P i fi = 2ε to show that f ≤ 2ε 3 . b) Prove that ε ≤ 3ν − 6. c) Use b) to show that K5 is not planar.
Let G be an undirected graph with n vertices and m edges. Use a contradiction argument...
Let G be an undirected graph with n vertices and m edges. Use a contradiction argument to prove that if m<n−1, then G is not connected
Let G be a simple graph with n(G) > 2. Prove that G is 2-connected iff...
Let G be a simple graph with n(G) > 2. Prove that G is 2-connected iff for every set of 3 distinct vertices, a, b and c, there is an a,c-path that contains b.
Question 38 A simple connected graph with 7 vertices has 3 vertices of degree 1, 3...
Question 38 A simple connected graph with 7 vertices has 3 vertices of degree 1, 3 vertices of degree 2 and 1 vertex of degree 3. How many edges does the graph have? Question 29 Use two of the following sets for each part below. Let X = {a, b, c}, Y = {1, 2, 3, 4} and Z = {s, t}. a) Using ordered pairs define a function that is one-to-one but not onto. b) Using ordered pairs define...
1) Describe an example of each of the following that may be found of your kitchen:...
1) Describe an example of each of the following that may be found of your kitchen: Explain how your choice falls into this category, and if there is a chemical name or symbol for it, provide that as well. Provide a photo of your example with your ID card in it. a) a compound b) a heterogeneous mixture c) an element (symbol) Moving to the Caves… Lechuguilla Caves specifically. Check out this picture of crystals of gypsum left behind in...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT