3
$\begingroup$

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.

enter image description here

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. enter image description here

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

From 3 to 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.

From 3 to 7

$\endgroup$
3
  • $\begingroup$ Thanks! Your answer is very in-depth. It solved my confusion.The another interesting thing is what properties a graph satisfies. Contracting any edge will not strictly increase the vertex connectivity. I don’t know if there are any research results on this issue. $\endgroup$ Commented May 2, 2021 at 5:34
  • $\begingroup$ I'm not sure what kind of research results you are after. From the answer we see that there can be an edge whose contraction increases connectivity, arbitrarily much. Of course there are other graphs where such edges do not exist. Also in one graph, some edges may increase connectivity when contracted, and some may not. Since you say "contracting any edge", are you seeking a graph such that for EVERY edge it is true that contracting it will increase connectivity? In contrast to these example graphs, where there just EXISTS an edge whose contraction increases connectivity? $\endgroup$ Commented May 3, 2021 at 7:49
  • $\begingroup$ @ Jukka Kohonen Due to the long talk, I added the relevant reply in the original text. $\endgroup$ Commented May 3, 2021 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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