characterisation of $2$-connected graphs with no even cycles

156 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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