CMI2011-B-02a

Question

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.

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

Answer 1

Every graph is a good graph. The proof is given below.

Suppose p be an maximal path in the graph G.
Let u and v be its end points.
Since p is the maximal path in the graph G all the neighbours of u and v will be on the path p.
So, if we remove either u or v from the path p then the neighbours of u or the neighbours of v remain connected through the path p.

Hence, after removing u or v from G the graph G remains connected.
Hence, for any graph we will get at least two vertices which are not cut vertices.

Hence every graph is a good graph (proved).

Now, in the question it is asked to prove the proposition

PROPOSITION :- A subgraph H of G is a good graph iff G is a good graph.

Now, according to the theorem ( Every graph is a good graph) we have both sides of the above proposition as true. (That is both sides of iff).

So, the above proposition is always true (proved).

Comments

1)U mean atlast path length will be $p-2$ , right?

2)Suppose p is path length 2 , means this x----------u------------y

Now if we remove x and y , is it still connected?

---

@Kushagra Chatterjee Still not clear. Plz tell me, what is answer for these two questions?