A graph $G$ is called *super connected* if for every connected subgraph $H\subset G$ the graph $G-H$ obtained from $G$ after deletion of all vertices from $H$ is also connected.



> 
> **Conjecture**: The only super connected graphs are $K\_{n}$ and $C\_{n}$.
> 
> 
> 


**ADDED 1:** Some related results can be found here <http://www.sciencedirect.com/science/article/pii/S0012365X96003068>


**ADDED 2:** See also the question [Graphs in which every spanning tree is an independency tree](https://mathoverflow.net/questions/141355/graphs-in-which-every-spanning-tree-is-an-independency-tree/141582#141582) for another interesting theme.



On "super connected" graphs
I think that conjecture is true. Let $a$, $b$ be two non-adjacent vertices. I claim that $H = G \setminus \{a, b\}$ must contain exactly two connected components. Indeed, if it has more than two, we can take any of these, say $H\_1$, and $H\_1 \cup \{a, b\}$ will be connected while the rest of $G$ not. On the other hand, the case of a single component $H$ is also impossible since otherwise $G \setminus H$ is just pair of vertices $a$ and $b$ and it is disconnected. Thus, $G$ consists of two components $H\_1$ and $H\_2$ and $a$ and $b$ in between. 


Now I claim that $H\_1$ is just a path from $a$ to $b$. First, since $G \setminus H\_2$ is connected, there should be some path $l$ from $a$ to $b$ which lies entirely in $H\_1$. On the other hand, $H\_1$ cannot contain any other vertices since otherwise $G \setminus \{l \cup a \cup b \}$ is disconnected. The same holds for $H\_2$. Thus, $G$ originally was just a cycle. 


