[Math] If a graph is k connected, then is it k+1 connected or k-1 connected? Or none

graph theoryproof-explanation

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.

Best Answer

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.

Related Question