2
$\begingroup$

Assertion: From any connected undirected graph it is possible to remove1 two adjacent edges such that the graph remains connected.

It is obvious that one can always remove1 one (and by induction, any number, one by one) of edges from a connected graph so that it remains connected. The assertion above is different from this in that one is speaking of removing two adjacent (sharing a common vertex) edges at any time. I was unable to find any counterexamples to the statement with brute force experiments, and I'm pretty convinced it is true. However, I'm struggling to prove it. Can anyone guide me in the right direction please? Note that the proof need not be constructive.

1 when removing an edge leaves a vertex with no more adjacent edges, that vertex is also considered removed

$\endgroup$
3
$\begingroup$

Let $G=(V,E)$ be a connected undirected graph.

If $G$ has two cycles $C_1, C_2$ that share a vertex $u$, you can find a vertex $v$ where the two cycles diverge, that is, $v\in C_1\cap C_2$ and there exist $v_1\in C_1\setminus C_1, v_2 \in C_2\setminus C_1$ such that $(v,v_1),(v,v_2)\in E$.

In this case you can safely remove $(v,v_1), (v,v_2)$ from $G$, since any path passing through $(v,v_i)$ can bypass through the remainder of $C_i$. $\square$

Two cycles sharing some vertices

If it does not contain two cycles that share a vertex, it means that all cycles are vertex-disjoint. Let's generalize the use of "cycle" in this context a little, and call any single vertex that's not a part of any larger cycle in $G$ a $1$-cycle, regarded as a cycle.

Let $C$ be a cycle. Any edge $e$ coming from $C$ thus goes to another cycle $D$. However, there can't be another $f$ edge between $C$ and $D$, as this would form a cycle passing through $e$ and $f$, which is not vertex-disjoint to $C$.

Construct the graph $G^\prime=(V^\prime,E^\prime)$ as a contraction of all cycles of $G$, where: $$V^\prime=\{c\subseteq V : c\mbox{ is a cycle in $G$}\}$$ $$E^\prime=\{(c_1,c_2) : \exists v_1\in c_1, v_2\in c_2 \left((v_1,v_2)\in G\right)\}$$

Finally, let $\varphi:G\to G^\prime$, defined $\varphi(v)=c$ if $v\in c$.

Observe that $G^\prime$ is a tree, since if it contains a cycle, this would not be edge-disjoint with all cycles of $G$ (unless it only touches $1$-cycles, in which case it would have been contracted).

Take any root $\rho$ of $G^\prime$ and find a leaf $c\in V^\prime$ of maximal depth with respect to $\rho$. Let $d$ denote the parent of $c$.

If $c$ is not a $1$-cycle, then there exists $v_1\in c$ which is not directly connected to $d$ (and consequently to anything outside $c$). You can remove $v_1$ and both of the edges around it and maintain the connectedness of $G$. $\square$

Removing two edges if $c$ is a true cycle

If $c$ is not a true cycle, but $d$ is, and if $\varphi^{-1}((c,d)) = (c,v_0)$, you can remove $(c,v_0)$ and $(v_0,v_1)$ for an adjacent $v_1\in d$. $\square$

Removing two edges if $c$ is not a true cycle but $d$ is

If neither are true cycles, and $c$ is the only child of $d$, remove $c$ and $d$, with all their edges. If $c$ has a sibling $c^\prime$, it will be childless, as $c$ is of maximal depth. Remove $c$ and $c^\prime$ with all their edges. $\blacksquare$

enter image description here

$\endgroup$

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.