# Covering and Cycles

Let $G = (V, E)$ and $G' = (V', E')$ be two graphs, and let $f: V \rightarrow V'$ be a surjection. Then $f$ is a covering map from $G$ to $G'$ if for each $v \in G$, the restriction of $f$ to the neighbourhood of $v$ is a bijection onto the neighbourhood of $f(v) \in V'$ in $G'$.

My question (homework) is how to easily prove that if there exists a cycle in $G$, there also exists a cycle in $G'$?

I have a proof based on the size of the preimage of each vertex of $G'$. But, it seems to complicate. I would like to know your point of view.

Thanks a lot in advance.

-

## 1 Answer

If $u,v\in V$ and $(u,v)\in E$ then since $u$ is in the neighborhood of $v$ then the condition on the local bijection gives you that $(f(v),f(u))\in E'$.

Suppose C is a cycle in G. Take the subgraph C' of G' with the vertices $f(v)$ such that $v\in C$ and the edges $(f(v),f(u))$ such that $(v,u)\in C$. If $u\in C$ then it has two different neighbors $v,w\in C$ so by the local bijection $f(u)$ has two different neighbors $f(v),f(w)$ in C'. By the definition of C' these are all the neighbors $f(u)$ has. So C' must be a cycle. (you can show that C' is connected, but even if it isn't you can say that every connected component is a cycle)

-