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 for another interesting theme.
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.
I was typing my solution when DmitryZ posted his more elegant one. Since the above solution is far shorter and more elegant than mine. I will just sketch my proof in case you are interested in related questions, and need a different aproach.
The sketch of my proof: As in DmitryZ's proof, if there are nonadjacent vertices a,b. Their deletion cuts the graph in exactly two connected components. There can not be vertices in those connected components with the property that: {after their deletion there is still a path using vertices in that component connecting a to b}. The components are trees. a and b can not have two neighbours in any of these components. Any leaves on these trees have to be adjacent either to a or b.
There is another proof that gives an alternative description of super connected graphs in terms of spanning trees (hence perhaps of interest):
The following statements are equivalent for any $n$-vertex graph $G$:
(i) $G$ is super connected.
(ii) $G$ is connected and in every spanning tree $T$ of $G$ every two leaves of $T$ are adjacent in $G$.
(iii) $G$ is the complete graph $K_n$ or the cycle $C_n$.
(i) $\Rightarrow$ (ii): This is because $T-a-b$ is connected, whenever $a$ and $b$ are two leaves in $T$.
(ii) $\Rightarrow$ (iii): Let $T$ be a depth-first-search (spanning-)tree of $G$, rooted at any vertex $v_0$. As the leaves of any DFS tree are pairwise non-adjacent in $G$, $T$ must be a Hamiltonian path, and the endvertices of $T$ must be adjacent in $G$. Thus, $G$ has a Hamiltonian cycle $C$, say $C: v_0v_1\ldots v_{n-1}v_0$. Assuming $G\not=C$, $C$ has a chord, say $v_0v_i$ for some $i \ge 2$. Write $A=\{v_{1},\ldots, v_{i-1}\}$, $B=\{v_{i+1},\ldots, v_{n-1}\}$. Then, first, every vertex in $A$ is adjacent to every vertex in $B$ because any $a\in A$ and any $b\in B$ are leaves in the spanning tree $C+v_0v_i-aa'-bb'$ of $G$, where $a'$, resp., $b'$ is a neighbor of $a$, resp., $b$ on $C$. Next, every two vertices $v_s, v_t\in A\cup\{v_0,v_i\}$, $s\le t-2$, are adjacent because, by the fact above, we have a chord $v_pv_q$ for any $v_p\in A$, $s<p<t$, and any $v_q\in B$, and hence, as above, $v_s$ and $v_t$ are two leaves of certain spanning tree of $G$. Similarly, every two vertices in $B\cup\{v_0,v_i\}$ are adjacent. It follows that $G=K_n$.
(iii) $\Rightarrow$ (i) is obvious.
