1
$\begingroup$

I would like to characterise $2$-connected graphs with no even cycles in them. And I would like to do it using ear decomposition.

Any hints?

$\endgroup$
  • $\begingroup$ Is it possible that the answer is just: The only ear is just an odd cycle? $\endgroup$ – tomak Jan 13 '18 at 16:23
1
$\begingroup$

I'll answer my own question:

The characterisation is as follows: $G$ is $2$-connected without even cycles iff it's ear decomposition is reduced to a non even cycle.

Indeed, the ear decomposition has at least a non even cycle $C$. If we add an ear $E$ to $C$, by choosing our two endpoints of $E$, $v_1$ and $v_2$ in $C$, the other vertices $v\in C$ will be split into two sets $A$ and $B$ "on the left" and "on the right" of $v_1$ and $v_2$. One of either $A$ or $B$ is odd and the other is pair.

Adding our ear, depending on wether it is of odd length or not and choosing the corresponding set $A$ or $B$ we will create an even cycle. So we have our contradiction

$\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.