Proof that if a biconnected component has AT LEAST ONE odd-length simple cycle, then ALL edges in such component are in some odd-length simple cycle?

Question

Is it true that if a biconnected component has at least one odd-length simple cycle, then ALL edges in such component belong to some (not necessarily the same) odd-length simple cycle? If that's the case, what would be a formal proof for that?

Answer 1

Yes, that statement is true. The main idea is that $$G\text{ has no odd-length simple cycle} \quad\Leftrightarrow\quad G\text{ is bipartite},$$ which comes up fairly often. Recall that $G$ is bipartite if there is a ''coloring'' of vertices $\chi : V(G) \to \{0,1\}$ such that every edge in $G$ joins vertices of opposite color. The implication $(\Rightarrow)$ holds because, assuming no odd cycles, we get a bipartite coloring using the naive/greedy algorithm.

Here is an argument:

Let $e $ be an edge with endpoints $x,y$ in a biconnected graph $G$. Suppose that $e$ does not belong in any odd-length simple cycle. Note that $C$ is a simple cycle containing $e$ if and only if $C \backslash e$ is a simple path connecting $x$ to $y$ in the deleted graph $G \backslash e$. Thus our assumption means that in $G\backslash e$, every simple path from $x$ to $y$ has an odd number of edges. Additionally, the assumption that $G$ is biconnected implies that $$ \text{every edge of $G\backslash e$ lies on a simple path in $G\backslash e$ from $x$ to $y$}. $$ (This is a common result in graph theory / matroid theory, but I don't remember a reference off hand.) This means we can assign a $2$-coloring of the vertices in $G\backslash e$, by alternating $0$'s and $1$'s along paths from $x$ to $y$. This coloring $\chi : V(G\backslash e) \to \{0,1\}$ satifies $$ \chi(v) = \begin{cases} 0 & \text{if $v$ is even distance from } x \quad(\text{odd dist. from } y)\\ 1 & \text{if $v$ is odd distance from } x \quad(\text{even dist. from } y). \end{cases}$$ In particular, $x$ and $y$ have opposite colors so this gives a bipartite coloring of $G$.

This shows that for biconnected $G$, $$ e\in E(G) \text{ belongs in no odd-length simple cycle} \quad\Rightarrow\quad G \text{ is bipartite}. $$ In particular, $G$ cannot have an odd-length cycle.