# Thread:

1. ## A problem on Graph theory and algorithms

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

2. ## Re: A problem on Graph theory and algorithms

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

As written this claim is false. (Unless you define subgraph differently than what I am assuming)
Counter: Let G be $P_5$ (a path on 5 vertices). Then clearly G is good. Let H be a subgraph created by removing a single vertex of degree 2 in G. Then H is disconnected and cannot be good. Hence the claim fails.

This is true if you say: for any connected subgraph H of G, H is good if and only if G is good. But you already proved a stronger statement than this, that all connected graphs are good.

3. ## Re: A problem on Graph theory and algorithms

Yes you are right...anyways thanks for pointing the counter eg ...

4. ## Re: A problem on Graph theory and algorithms

How to prove that Hamming graph H(d,3) has a diameter d?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 1, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9429603219032288, "perplexity_flag": "middle"}