I am just wondering what can we conclude further if a graph is $k-\text{vertex}$ $-\text{ connected}$. This is just my personal doubt.

Before that I want to clarify the definition:

According to Wikipedia, it should has more than k vertices and remains connected whenever fewer than k vertices are removed. From my understanding, the definition implies that there is a way to remove k vertices to disconnect the graph. I want to clarify by "whenever" does it mean "any". Is it correct if I rephrase it as "it remains connected even if we remove any less than k vertices, but it can be disconnected if we remove k vertices"?

Now, I am wondering whether any of these statements is true?

  1. If a graph is $k-\text{vertex}$ $-\text{ connected}$ then it is $(k+1)-\text{vertex}$ $-\text{ connected}$.

  2. If a graph is $k-\text{vertex}$ $-\text{ connected}$ then it is $(k-1)-\text{vertex}$ $-\text{ connected}$.

In my opinion both are wrong, but I am not sure. Here are my reasons:

  1. If a graph is $k-\text{vertex}$ $-\text{ connected}$ and if it is also $(k+1)-\text{vertex}$ $-\text{ connected}$ then there are $k$ vertices that you can remove to disconnect the graph which contradicts the definition of $(k+1)-\text{vertex}$ $-\text{ connected}$.

  2. If a graph is $k-\text{vertex}$ $-\text{ connected}$ and if it is also $(k-1)-\text{vertex}$ $-\text{ connected}$ then there are $k-1$ vertices that you can remove to disconnect the graph, but again it contradicts the definition of $k-\text{vertex}$ $-\text{ connected}$.

The reason why I asked the above questions is because I encountered a proof about the statement "Suppose that $G$ is a nonplanar graph, $G$ contains no Kuratowski subgraphs, and that $G$ is minimally nonplanar. Then G is at least 3-connected."

The proof says:

We again proceed by contradiction. Take any such graph G. We know from our earlier proposition that this graph is at least 2-connected; let's assume for contradiction that it is exactly two-connected, and therefore that there is some pair of vertices $x$; $y$ such that deleting $x$ and $y$ from our graph disconnects it.

What confuses me is why do we need exactly 2-connected for a contradiction? The assumption says that it is at least 2-connected, the negation of that statement should be at most 1-connected, isn't it? I really need to understand what does at least 2-connected imply to really understand the logic of the contradiction.

Thanks for the help. It really confuses me.


The definition implies no such thing. There is no such thing as "implying" in definitions. The definitions state what they explicitly state, and nothing more and nothing less.

For example, if I say I am taller than $150$ centimeters, I do not imply that I am shorter than $151$ centimeters. The definition simply says that

No matter how you remove fewer than $k$ vertices, the graph remains connected.

This means that it should be easy for you to show that if a graph is $k$-connected, then it is also $k-1$ connected.

The reverse is of course not true, but your proof is not good. What you have "proven" is that a graph cannot be both $k$-connected and $k+1$ connected, which is not true (a counterexample of that is a full graph on $k+2$ vertices, for example)

There is also the concept of exact $k$-connectedness, and a graph is $k$-connected if it is $k$ connected, but it is not $k+1$ connected (and, consequently, the graph is $1,2,3,\dots,k$ connected, and is not $k+1,k+2,k+3\dots$-connected)

This is the concept used in your proof. You already know that the graph is $2$ connected (so it is also $1$ connected), now it can either be exactly $2$ connected or not. The proof shows that the graph cannot be exactly $2$ connected, so it must be $3$ connected.

  • $\begingroup$ Is there any other stronger definition of $k-$connected that says it is possible to have $k$ vertices removed for the graph to be disconnected? I think that definition is a bit too weak, I find it hard to use that in a proof. $\endgroup$ – user338393 Jun 7 '16 at 7:20
  • 1
    $\begingroup$ @user338393 Read my answer to the end. $\endgroup$ – 5xum Jun 7 '16 at 7:21

A graph is $k$-connected if it has at least $k+1$ vertices and the removal of $k-1$ or fewer vertices leaves a connected graph. For example, the star graph $K_{1,4}$ has a center vertex whose removal disconnects the graph. So the star graph is not 2-connected. However, it is 1-connected because it is connected. The cycle graph $C_6$ is 2-connected because the removal of any vertex leaves a path graph on 5 vertices which is a connected graph. Clearly, the cycle graph $C_6$ is also 1-connected since it is connected. The cycle $C_6$ is not 3-connected because removing the first and third vertex disconnects the graph and isolates the second vertex.

If removing any $k-1$ vertices leaves a connected graph, then removing any $k-2$ vertices also leaves a connected graph. Thus, it follows from the definition that if a graph is $k$-connected, then the graph is also $(k-1)$-connected. The converse is not true in general, as we saw above: $C_6$ is 2-connected but not 3-connected. Of course, $C_6$ is 1-connected and also 2-connected, but if you pick the value of $k$ to be largest possible, then we can't go from $k$ to $k+1$ (but we can obviously go from $k$ to $k-1$). In fact, the maximal value of $k$ for which a graph is $k$-connected is called the vertex-connectivity of the graph. For example, the vertex-connectivity of $C_6$ is equal to 2.


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.