edited by
547 views
3 votes
3 votes
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.
edited by

1 Answer

1 votes
1 votes
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).

Related questions