Let G be a simple graph with 20 vertices and 8 components. If we delet...
Case 1: If the vertex we are deleting from G is an isolated vertex, which is a component by itself, then number of components in G becomes 7.
Case 2: If G is a start Graph, then by deleting the cut vertex of G, we get 19 components.
Hence, number of components in G should lie between 7 and 19.
View all questions of this test
Let G be a simple graph with 20 vertices and 8 components. If we delet...
To understand why the number of components in graph G should lie between 7 and 19 when a vertex is deleted, let's break down the problem step by step.
Given:
- Graph G is a simple graph with 20 vertices.
- Graph G has 8 components.
Components in a Graph:
- In a graph, a component is a subgraph where every pair of vertices is connected by a path.
Key Observation:
- The maximum number of components possible in a simple graph with n vertices is n.
- In the given problem, the number of vertices in graph G is 20, so the maximum number of components possible is 20.
Deleting a Vertex:
- When a vertex is deleted from a graph, the edges connected to that vertex are also removed.
- Deleting a vertex can potentially break the connectivity of the graph, resulting in an increase in the number of components.
Minimum Number of Components:
- The minimum number of components that can be obtained after deleting a vertex is when the deleted vertex is not a part of any cycle or connected to any other vertices.
- In this case, deleting the vertex will result in no change in the number of components.
- Therefore, the minimum number of components will be the same as the initial number of components, which is 8.
Maximum Number of Components:
- The maximum number of components that can be obtained after deleting a vertex is when the deleted vertex is a part of every cycle or connected to every other vertex.
- In this case, deleting the vertex will break the connectivity, resulting in each vertex becoming a separate component.
- Therefore, the maximum number of components will be equal to the number of vertices in the graph, which is 20.
Conclusion:
- After deleting a vertex in graph G, the number of components can range from a minimum of 8 to a maximum of 20.
- Thus, the correct answer is option 'c' which states that the number of components in G should lie between 7 and 19.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).