2
$\begingroup$

By going over the tests of previous years in graph theory, I've come across an interesting (in my opinion) question:

$G$ is 3-connected, non-bipartite graph. Prove that $G$ contains at least 4 odd cycles.

I tried the following way: as $G$ is non-bipartite, it has an odd cycle $C$. Now, since $G$ 3-connected, there should be $v \in V(G-C)$ with 3 paths to $C$. From here it should be a game of combining odd/even paths, to get what is needed. But there are too much options.

Is there any other way?

Thanks.

  • 0
    @Pavel It has to be paths in $G-C$ from $v$ to each vertex of the cycle because otherwise the graph wouldn't be 3-connected (since removing the 2 vertices in the cycle next to one without path to $v$, the graph would get disconnected). Then you can decompose the cycle as you want.2012-08-24

0 Answers 0