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


closed as off-topic by The Count, Shailesh, Mars Plastic, YuiTo Cheng, Thomas Shelby Aug 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.

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

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.

  • $\begingroup$ Your assumptions and answer are correct.Thank you so much. $\endgroup$ – Farshad Hasani Aug 1 at 15:28

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