A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...

Question

Question

A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for its Minimum Vertex Cover of G? at

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

a) Since 4 vertices are pair-wise disjoint, between those vertices there is no edge.

And any other vertex should have an edge to atleast one of the vertex from this set or else pair-wise

disjoint vertices becomes 5.

So, atleast these 4 vertices are needed for minimum vertex cover.

b) And since they don't have any edge among them, By selecting all other 8 vertices we can cover all the

edges.

Hence, minimum cover can be atmost 8.

Add a comment

Answer 2

Similar Homework Help Questions

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could be said about its minimum vertex cover of G? It has... Yes No Impossible to determine a) at least 4 vertices because Yes No Impossible to determine b) at most 8 vertices because
#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could be said about its minimum vertex cover of G? It has... Yes No Impossible to determine a) at least 4 vertices because Yes No Impossible to determine b) at most 8 vertices because
#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could be said about its minimum vertex cover of G? It has... Yes No Impossible to determine a) at least 4 vertices because Yes No Impossible to determine b) at most 8 vertices because

Draw a Graph with 12 vertices which has 4 pair-wise nonadjacent vertices.

Draw a Graph with 12 vertices which has 4 pair-wise nonadjacent vertices.
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 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...

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...
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...
(Problem R-14.16, page 678 of the text) Let G be a graph whose vertices are the...

(Problem R-14.16, page 678 of the text) Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below: Vertex adjacent vertices 1 (2,3,4) 2 (1,3,4) 3 (1,2,4) 4 (1,2,3,6) 5 (6,7,8) 6 (4,5,7) 7 (5,6,8) 8 (5,7) Assume that, in a traversal of G, the adjacent vertices...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u)...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u) +8()2 k, for some k> O. Show that G contains a path of length k. Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u) +8()2 k, for some k> O. Show that G contains a path of length k.

A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...

Homework Answers

Add Answer to:
A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...

Post as a guest

Earn Coins

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

#2. Answer with explanations. Graph G with 12 vertices has 4 pair-wise nonadjacent vertices. What could...

Draw a Graph with 12 vertices which has 4 pair-wise nonadjacent vertices.

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...

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...

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...

(Problem R-14.16, page 678 of the text) Let G be a graph whose vertices are the...

Let G be a non-Hamiltonian, connected graph. For every pair of nonadjacent vertices u and v, 8(u)...

A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...

Homework Answers

Add Answer to: A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...

Post as a guest

Earn Coins

Add Answer to:
A graph (G) with 12 Vertices has 4 PAIR-WISE non-Adjacent Vertices, What could be said for...