Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.