Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...

Question

Question

Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar embedding G C R2 dividing the plane R2

math Advanced-Math

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

According to Euler's formula for any planar graph with v vertices, f faces & e edges then,

v-e+f =2

so,here v=12 ,f=20

12- e+20=2

=> e = 20+12-2 =30

Add a comment

Answer 2

Similar Homework Help Questions

(a) Suppose that a connected planar graph has six vertices, each of degree three. Into how...

(a) Suppose that a connected planar graph has six vertices, each of degree three. Into how many regions is the plane divided by a planar embedding of this graph? 1. (b) Suppose that a connected bipartite planar simple graph has e edges and v vertices. Show that є 20-4 if v > 3.
Let G be a connected graph with n vertices and n edges. How many cycles does...

Let G be a connected graph with n vertices and n edges. How many cycles does G have? Explain your answer.
Question 16. A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. (a) Draw a maximal plane graphs...

Question 16. A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. (a) Draw a maximal plane graphs on six vertices. (b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. (c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a...

Let G -(V, E) be a graph. The complementary graph G of G has vertex set V. Two vertices are adjacent in G if and only if they are not adjacent in G. (a) For each of the following graphs, describe its...

Let G -(V, E) be a graph. The complementary graph G of G has vertex set V. Two vertices are adjacent in G if and only if they are not adjacent in G. (a) For each of the following graphs, describe its complementary graph: (i) Km,.ni (i) W Are the resulting graphs connected? Justify your answers. (b) Describe the graph GUG. (c) If G is a simple graph with 15 edges and G has 13 edges, how many vertices does...
A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. a) Draw a maximal plane graphs on six vertices. b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon...
A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. A maximal plane graph is a plane graph G = (V, E) with n-3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. (a) Draw a maximal plane graphs on six vertices b) Show that a maximal plane graph...

solve with steps 1. (20 points) True or false. Justify. Every planar graph is 4-colorable /2 The number of edges in a simple graph G is bounded by n(n 1) where n is the number of vertices. The number...

solve with steps 1. (20 points) True or false. Justify. Every planar graph is 4-colorable /2 The number of edges in a simple graph G is bounded by n(n 1) where n is the number of vertices. The number of edges of a simple connected graph G is at least n-1 where n is the number of vertices. Two graphs are isomorphic if they have the same number of vertices and 1) the same mumber of edges 1. (20 points)...
(a) Let G be a graph with order n and size m. Prove that if (n-1)...

(a) Let G be a graph with order n and size m. Prove that if (n-1) (n-2) m 2 +2 2 then G is Hamiltonian. (b) Let G be a plane graph with n vertices, m edges and f faces. Using Euler's formula, prove that nmf k(G)+ 1 where k(G) is the mumber of connected components of G. (a) Let G be a graph with order n and size m. Prove that if (n-1) (n-2) m 2 +2 2 then...
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then...

49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is connected. b. Show that the result in (a) is best possible; that is, for each n 2 2, prove there is a graph with ("2) edges that is not connected. 49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is...

Please answer only problem 2. Accurate answers with work shown will receive a 100% rating ASAP....

Please answer only problem 2. Accurate answers with work shown will receive a 100% rating ASAP. Thank you! Let G = (V, E) be a graph. We say that a subset S of the vertices V is an independent set if there is no edge in G joining two vertices in S. For example, given a proper colouring of the vertices of G, each colour class (i.e. the set of vertices that have some fixed colour) forms an independent set,...

Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...

Homework Answers

Add Answer to:
Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...

Post as a guest

Earn Coins

(a) Suppose that a connected planar graph has six vertices, each of degree three. Into how...

Let G be a connected graph with n vertices and n edges. How many cycles does...

Question 16. A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. (a) Draw a maximal plane graphs...

Let G -(V, E) be a graph. The complementary graph G of G has vertex set V. Two vertices are adjacent in G if and only if they are not adjacent in G. (a) For each of the following graphs, describe its...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices...

solve with steps 1. (20 points) True or false. Justify. Every planar graph is 4-colorable /2 The number of edges in a simple graph G is bounded by n(n 1) where n is the number of vertices. The number...

(a) Let G be a graph with order n and size m. Prove that if (n-1)...

49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then...

Please answer only problem 2. Accurate answers with work shown will receive a 100% rating ASAP....

Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...

Homework Answers

Add Answer to: Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...

Post as a guest

Earn Coins

Add Answer to:
Problem 2. Let G be connected graph with 12 vertices. Suppose that it admits an planar...