If $G,H$ are simple, undirected graphs, we say that they are in a *hom(omorphism)-relation* if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$.


For any graph $G$ let $L(G)$ denote its [line graph](https://en.wikipedia.org/wiki/Line_graph).


If $G,H$ each have at least one edge, and they are in a hom-relation, does the same hold for $L(G), L(H)$?



Graph homomorphisms and line graph
Well, this question turned out more interesting than I thought at first.


If there is a homomorphism $f:G \to H$ then at first sight, it seems that the natural induced mapping on edges would be a homomorphism from $L(G) \to L(H)$, but this turns out to be false.


In fact, the whole thing turns out to be false, in that two graphs can be homomorphically equivalent (i.e. homomorphisms in both directions), but have unrelated linegraphs. 


I think that the smallest examples are the following two, and running this Sage code is the easiest way to convince yourself that they are actually examples.



```
g1 = Graph("D]w")
g2 = Graph("FQjR_")
lg1 = g1.line_graph()
lg2 = g2.line_graph()
g1.has_homomorphism_to(g2)
g2.has_homomorphism_to(g1)
lg1.has_homomorphism_to(lg2)
lg2.has_homomorphism_to(lg1)

```

Actually, the two graphs both have chromatic number 3 and have triangles, so it is easy to see that they are homomorphically equivalent (simply use the colour classes to map each one into one of the triangles of the other). 


But it is not trivial to see that the two linegraphs do *not* have homomorphisms between them. Or at least, I couldn't find a slick one-or-two line reason for it, and rather than start to write out a case analysis (suppose vertex 1 is mapped to vertex 2, then vertex 2 must be mapped to either 3 or 4, and in the first case...), the Sage code is easier to understand and more reliable.


