# On "super connected" graphs

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.

• Usually a graph is called superconnected if every minimal vertex cut isolates a vertex of G. Your definition is different, right? Aug 23 '13 at 11:23
• Please define $G-H$. If it just means that the edges of $H$ are removed from $G$, then $K_n$ is not an example. Sep 7 '13 at 3:27

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.

• Dear DmitryZ! I think that your proof is correct. Thanks. And let the spirit of Erdos come with you! Aug 23 '13 at 14:01
• "we can take any of these, say $H_1$, and $H_1 \cup \{a, b\}$ will be connected..." As far as I understand, we should take a component $H_1$ such that $H_1 \cup \{a, b\}$ is connected. It is not automatically. Aug 23 '13 at 14:49
• @AntonKlyachko You're right, there should be at least one. Aug 23 '13 at 15:07
• A couple comments. The claim is in fact true for all components of $G \setminus \{a,b\}$. If there was a component that was only connected to $a$, then $G \setminus a$ would be disconnected (the subgraph consisting of just $a$ is connected). Aug 24 '13 at 23:31
• Also, you want to take $l$ to be a shortest path from $a$ to $b$ in $G[V(H_1) \cup \{a,b\}]$. While it is true that there are no other vertices in $l$, if you do not take a shortest path, then there may be other edges (between vertices of $l$). Aug 24 '13 at 23:35

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, 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.

• Thanks for another equivalent statement. That's interesting! Aug 30 '13 at 13:07