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.

  • $\begingroup$ Usually a graph is called superconnected if every minimal vertex cut isolates a vertex of G. Your definition is different, right? $\endgroup$ – DmitryZ Aug 23 '13 at 11:23
  • $\begingroup$ Please define $G-H$. If it just means that the edges of $H$ are removed from $G$, then $K_n$ is not an example. $\endgroup$ – Brendan McKay 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.

  • 1
    $\begingroup$ Dear DmitryZ! I think that your proof is correct. Thanks. And let the spirit of Erdos come with you! $\endgroup$ – Sergiy Kozerenko Aug 23 '13 at 14:01
  • 2
    $\begingroup$ "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. $\endgroup$ – Anton Klyachko Aug 23 '13 at 14:49
  • $\begingroup$ @AntonKlyachko You're right, there should be at least one. $\endgroup$ – DmitryZ Aug 23 '13 at 15:07
  • 2
    $\begingroup$ 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). $\endgroup$ – Tony Huynh Aug 24 '13 at 23:31
  • $\begingroup$ 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$). $\endgroup$ – Tony Huynh 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<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.

  • 3
    $\begingroup$ Thanks for another equivalent statement. That's interesting! $\endgroup$ – Sergiy Kozerenko Aug 30 '13 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.