edited by
571 views
1 votes
1 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 there exists a graph $H$ such that we cannot find three distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,$ and  $G − u_3$ is connected.
edited by

1 Answer

Best answer
2 votes
2 votes

We can make a linear graph like below:


Removing A or D keeps the graph connected. But removing B or C disconnects the graph.

We cannot find three vertices to make this graph good.

selected by

Related questions