Which graphs remain connected when any connected subgraph is removed?

Question

Which graphs remain connected when any connected subgraph is removed? For example, complete graphs; $K_n$ or cyclic graphs; $C_n$ , fulfill this. Can someone give an example of another that is neither cyclical nor complete?

Answer 1

Let $G$ be a graph. I will call a nonempty subset $X\subset V(G)$ connected if it induces a connected subgraph of $G$.

I claim that, if $G$ is connected, and if $G-X$ is connected for every connected proper subset $X\subset V(G)$, then $G$ is either a complete graph or a cycle graph.

Suppose $G$ is not a complete graph. Choose two nonadjacent vertices $u,v\in V(G)$, and suppose $G-\{u,v\}$ has $n$ connected components $X_1,X_2,\dots,X_n$. Note that $X_i\cup\{u,v\}$ is connected; for, if $u$ were not connected to $X_i$, then $G-\{v\}$ would be disconnected.

Plainly $n\ge1$, since $G$ is connected.

Moreover $n\ge2$, since $G-X_1$ is connected.

But we can't have $n\gt2$, since $G-(X_1\cup\{u,v\})$ is connected.

So $G-\{u,v\}$ has exactly two connected components, $X=X_1$ and $Y=X_2$.

Let $u,x_1,\dots,x_r,v$ be a shortest (therefore chordless) $u,v$-path in $X\cup\{u,v\}$. Note that $\{x_1,\dots,x_r\}=X$, since $G-\{u,x_1,\dots,x_r,v\}$ is connected.

Likewise, there is a chordless $v,u$-path $v,y_1,\dots,y_s,u$ such that $\{y_1,\dots,y_s\}=Y$.

As there are no edges $x_iy_j$, it's clear that $G$ is a cycle graph of length $r+s+2$.

P.S. Of course this result follows from Misha Lavrov's answer to your other question, since $K_{1,1}$ is a complete graph, and $K_{2,2}$ is a cycle graph, and for $n\ge3$ the graph $K_{n,n}$ can be disconnected by removing the connected subgraph $K_{1,n}$. So Misha Lavrov's argument shows that any graph except a complete graph or a cycle graph can be disconnected by removing either a path or a star.