3
$\begingroup$

I am trying to prove the following statement:

An edge $e$ in a 2-connected graph $e$ is said to be contractible if $G/e$ is also 2-connected. Prove that every 2-connected graph of order at least 3 has at least one contractible edge.

I know that it's a well known result that every edge in a 2-connected graph is either contractible or deletable, however I would like to prove the statement without using this theorem.

My approach so far has been: first, prove that an edge $e = xy$ is contractible if and only if $\{x,y\}$ is not a vertex cut of the graph. Next, prove that any 2-connected graph with at least 3 vertices has at least one edge such that its vertices do not form a vertex cut. The first part was relatively easy, however I'm having quite a bit of trouble with the second part.

Some other ideas I've considered are showing that the ear decomposition of $G$ must have an edge such that deleting both vertices does not affect the connectivity of the graph or showing that there must be a spanning tree of $G$ with a leaf such that its adjacent vertex has only two neighbors and therefore deleting both vertices doesn't disconnect the graph.

Any ideas on this, including alternative approaches, would be greatly appreciated.

$\endgroup$
2
  • $\begingroup$ I'm thinking out loud here: Since any $2$-connected graph $G$ (is non-separable) of order at least $3$, pick any two distinct vertices $u$ and $v$ such that $uv \notin E(G)$. Then the vertices $u$ and $v$ should lie on a common cycle; does the contraction $G\e$ where $e = ux$ not produce another non-separable graph? $\endgroup$
    – user333821
    Oct 15, 2021 at 11:01
  • $\begingroup$ I believe then it would come down again to whether $\{u,x\}$ is a vertex cut, since if it is then in $G/e$ the vertex resulting from contracting $e$ would be an articulation point. $\endgroup$
    – dixego
    Oct 15, 2021 at 15:09

1 Answer 1

Reset to default
3
$\begingroup$

Consider an open ear decomposition of $G$ and let $C$ be the last proper ear (that is not just an edge) added. Then you can contract any edge of this ear, and the ear decomposition structure shows that the resulting graph is still $2$-connected.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .