# For a three-connected graph, is there a contraction edge that strictly increases vertex connectivity?

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. edge contraction

As defined below, an edge contraction operation may result in a graph with multiple edges even if the original graph was a simple graph. In my problem here, we need to delete all multiple edges. I am considering the relationship of edge contraction on vertex connectivity between $$G$$ and $$G/e$$. Under normal circumstances, it may decrease or increase, or it may not change. I am interested in which shrinking edges cause the increase strictly on vertex connectivity. I feel the following is right. But I can’t strictly prove it. Probably we can find counterexamples.

For a three-connected graph, contraction of any edge cannot strictly increase the vertex connectivity.

With regard to the relationship between contraction edges and vertex connectivity, what are the known results?

Edit: According to Jukka Kohonen’s wonderful answer, we know that above proposition for $$3$$ connected graph is wrong.

The motivation for my thinking comes from the Thomassen theorem.

Every $$3$$-connected graph $$G$$ with more than $$4$$ vertices has an edge e such that $$G/e$$ is also 3 -connected.

I'd like to study more clearly the relationship between edge contraction and vertex connectivity of graphs.

For example. From observation of answer of Jukka Kohonen, the following proposition may be correct.

Let $$G$$ is a $$2$$-connected graph and $$S$$ is its minimal vertex cut. If there are at least two non-trivial connected components of $$G-S$$, then contracting any edge of $$G$$ will not strictly increase the vertex connectivity of $$G$$.

Of course, maybe we can also find counterexamples. I think it’s also interesting for the question mentioned in the reply.

Seeking a graph such that for EVERY edge it is true that contracting it will increase connectivity

But I haven't thought too much about it.

The 6-vertex graph below, on the left, has vertex connectivity 3. Contracting edge $$(4,5)$$ turns it into a $$K_5$$, which has vertex connectivity 4. In fact, connectivity can increase as much as you like. Make a clique of $$a+b$$ vertices, then create two more vertices $$u$$ and $$v$$, connecting $$u$$ to $$a$$ of the original vertices, $$v$$ to the other $$b$$ of them, and $$u,v$$ to each other. If $$a \le b$$, this has connectivity $$a+1$$, but contracting edge $$uv$$ turns it into a $$K_{a+b+1}$$ that has connectivity $$a+b$$. The following image shows it with $$a=2$$ and $$b=5$$, so connectivity goes from 3 to 7. 