# homomorphism between Petersen graph and $C_5$ [closed]

Why $$\text{Hom}(\text{Petersen graph}, C_5)=\emptyset$$ ?

## closed as off-topic by The Count, Shailesh, Mars Plastic, YuiTo Cheng, Thomas ShelbyAug 1 at 15:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – The Count, Shailesh, Mars Plastic, YuiTo Cheng, Thomas Shelby
If this question can be reworded to fit the rules in the help center, please edit the question.

• What is $\text{Hom}(\text{a graph}, \text{another graph})$? – Magma Aug 1 at 14:44
• all of homomorphisms between a graph and another graph. – F. Hasani Aug 1 at 14:49
• Does that mean surjective homomorphisms? – saulspatz Aug 1 at 14:49
• No, for any homomorphism. – F. Hasani Aug 1 at 14:54

## 1 Answer

Assuming that by $$\text{Hom}$$ you mean the set of graph homomorphisms of graphs, and that the graphs in question do not have loops.

First of all, consider homomorphisms from $$C_5$$ to $$C_5$$. It should be easy to observe that all such homomorphisms are necessarily bijective.

Assume that $$\text{Hom}(\text{Petersen graph},C_5)$$ set is nonempty, and there is a homomorphism $$h$$ in that set. Choose the 5-cycle $$ABCDE$$ in the Petersen graph. Let's set $$h(A) =: V, h(B) =: W, h(C) =: X, h(D) =: Y, h(E) =: Z$$. Note that $$VWXYZ$$ are the vertices of $$C_5$$ in order, because of our previous observation.

Now the Petersen graph contains another 5-cycle $$ABCFG$$, where $$F, G$$ are not the same as $$D, E$$. By necessity, $$h(F) = Y, h(G) = Z$$.

But now the Petersen graph contains another 5-cycle $$DEAGH$$, where $$H$$ is a new vertex. Since $$H$$ is adjacent to $$D$$ and $$G$$, $$h(H)$$ must be adjacent to $$h(D) = Y$$ and $$h(G) = Z$$. But there is no such vertex in $$C_5$$ adjacent to $$Y$$ and $$Z$$ simultaneously. This is a contradiction, so our assumption that $$h$$ exists is false.

• Your assumptions and answer are correct.Thank you so much. – F. Hasani Aug 1 at 15:28