In a bipartite graph, any cycle of length equal to the girth is a retract.

Question

This is an exercise from the book Algebraic Graph Theory by Godsil and Royle.

Show that in a bipartite graph, any cycle of length equal to the girth is a retract.

We say that a subgraph $Y$ of $X$ is a retract, if there is a homomorphism $f:X\to Y$ such that $f|Y$ is the identity map.

I have no idea how to approach this, I can gather a few things from the graph being bipartite, such as that the girth must be even, or that there is a homomorphism from it to $K_2$. But I'm having a hard time piecing it together.

Answer 1

Hint: consider a vertex on the minimum length cycle, and label the other vertices of the graph by their distance from it. See if you can use this to define a retraction. (Basically, use the previous exercise in the book).

You may also find it helpful to know that, if $u$ is any vertex of a connected bipartite graph, then the vertices even distance from $u$ are one partite set of $G$, and the vertices odd distance from $u$ are the other partite set.

Proof sketch:

Let $C = v_0, v_1, \dots, v_{k-1}$ be a minimum length cycle in $G$. For $u\in G$, define a label $j: V(G)\to \mathbb{N}$ by: $$j(u) = \begin{cases}d(v_0, u) &\text{ if } d(v_0,u) < k\\ k-1 &\text{ if }d(v_0,u)\geq k,\text{ and } d(v_0,u)\text{ is even}\\k-2 &\text{ if }d(v_0,u)\geq k,\text{ and } d(v_0,u)\text{ is odd}\end{cases}$$ Then we define a retraction $r:V(G)\to V(C)$ by $r(u) = v_{j(u)}$. I'll leave you to check that it's a retraction. In fact, this map $r$ is even a retraction from $G-\{v_0v_{k-1}\}$ onto the path $C-\{v_0v_{k-1}\}$.