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
    @Graphth: Given the statement that Pavel wants to prove, it seems likely that *bipartite* in the third paragraph is a typo for *non-bipartite*.2012-08-24
  • 0
    Sorry, indeed. Fixed.2012-08-24
  • 0
    @Pavel I assume you admite any 4 odd cycles, because if you want they to be independent, then the 3-regular graph of 4 vertices would not satisfy the claim.2012-08-24
  • 0
    @iago Yes, I think that was the intention.2012-08-24
  • 0
    @Pavel Following your idea, you can reduce the combinations of the paths to only 3 options (not too much). Decomposing the cycle in 3 odd-lenght paths you may assume that it has lenght 3 (the important is just parity). Now take $v$ at distance 1 of a vertex of the cycle. Then the only combinations you have to consider if the 2 paths to the other vertices of the cycle are odd-odd, even-even or even-odd.2012-08-24
  • 0
    @iago I think there is more to that. I'm not sure how you can decompose the cycle, before you know where the paths from $v$ will go. The decomposition, as I see it, is made by them. And then, you'll need to take the parities of this decomposition into account too.2012-08-24
  • 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