Problem on Graph Theory and Algorithms

[Chinta]

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.

Please help me in solving part(i).

Thanks in advance :)

 

[Sudharaka]

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.

Please help me in solving part(i).

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]

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

Anyway thanks for your solution too.

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