1
$\begingroup$

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 Answers 1

1

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)