Problem on Graph Theory and Algorithms

Chinta

New member
The problem is as follows:
---------------------------------------------------------------------------------------------------------------------------------
Let G be a connected graph.

For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is said to be good if there are at
least two distinct vertices x,y in G such that both G − x and G − y are connected.

(i) Show that for any subgraph H of G, H is good if and only if G is good.

(ii) Given a good graph, devise a linear time algorithm to find two such vertices.

(iii) Show that there exists a graph G such that we cannot find three distinct vertices
u1,u2,u3such that each of G − u1,G − u2, and G − u3 is connected.
---------------------------------------------------------------------------------------------------------------------------------
I have approached to some extent. Here is what I've done:

If G is a connected graph then we can easily find its spanning tree and then removing any two leaves x and y from the tree one at a time gives us 2 another graphs G − x and G − y such that they are both connected.

"Hence any connected graph G is a good graph."

1. I'm stuck on how to solve part (i).

2. I have designed the algorithm for the part(ii) which extracts the spanning tree from G and then finds two such leaves x and y. Clearly
it is linear in terms of #vertices(=n) & #edges(=m) i.e. O(n+m)

3. I have also solved the third part with a graph as follows:

O------------------O-----------------O

In the above graph G we denote three vertices as u1, u2, u3. The edges are (u1,u2) and (u2,u3). Clearly G − u2 is not connected.

Thanks in advance Sudharaka

Well-known member
MHB Math Helper
The problem is as follows:
---------------------------------------------------------------------------------------------------------------------------------
Let G be a connected graph.

For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is said to be good if there are at least two distinct vertices x,y in G such that both G − x and G − y are connected.

(i) Show that for any subgraph H of G, H is good if and only if G is good.

(ii) Given a good graph, devise a linear time algorithm to find two such vertices.

(iii) Show that there exists a graph G such that we cannot find three distinct vertices
u1,u2,u3such that each of G − u1,G − u2, and G − u3 is connected.
---------------------------------------------------------------------------------------------------------------------------------
I have approached to some extent. Here is what I've done:

If G is a connected graph then we can easily find its spanning tree and then removing any two leaves x and y from the tree one at a time gives us 2 another graphs G − x and G − y such that they are both connected.

"Hence any connected graph G is a good graph."

1. I'm stuck on how to solve part (i).

2. I have designed the algorithm for the part(ii) which extracts the spanning tree from G and then finds two such leaves x and y. Clearly
it is linear in terms of #vertices(=n) & #edges(=m) i.e. O(n+m)

3. I have also solved the third part with a graph as follows:

O------------------O-----------------O

In the above graph G we denote three vertices as u1, u2, u3. The edges are (u1,u2) and (u2,u3). Clearly G − u2 is not connected.

Thanks in advance Hi Chinta, I think the first statement that you want to prove is in fact a false statement. For example take $$H=C_{4}$$ where $$C_{4}$$ is the cycle graph of four vertices. Now let $$G$$ be the graph obtained by adding a single vertex to $$H$$. Then it is clear that $$H$$ is a sub-graph of $$G$$. However, $$H$$ is a good graph but $$G$$ is not a good graph.

By the way can you please tell me where you found this question? Kind Regards,
Sudharaka.

Chinta

New member
Actually I've got this answer that the question was wrong right after I posted the problem here a long time ago...I myself figured it out but forgot to post it here. Anyway thanks for your solution too.

I got this question from a graph theory tutorial in internet actually.