Two graphs $G$ and $G^{\prime}$ are said to be graph isomeric if the share the same number of vertices and edges. If there is a graph homomorphism $h \colon G \to G^{\prime}$ between graph isomers which preserves vertex degree, can one conclude that $G$ and $G^{\prime}$ are graph isomorphic?
Graph Isomerism and Isomorphism
1
$\begingroup$
graph-theory
-
1I never know what people's conventions for graph homomorphisms are. Are they just maps from vertices to vertices that preserve the relation given by edges? Are vertices considered related to themselves for the purposes of this relation? – 2012-08-06
-
1I'm using [this](http://en.wikipedia.org/wiki/Graph_homomorphism) definition of homomorphism. – 2012-08-06
1 Answers
5
$$1-2-1 \quad 1-2-1$$
is not isomorphic with $$1-1 \quad 1-2-2-1$$
But they are isomeric and there is a trivial homomorphism. There are plenty of other examples...
-
0Sorry, what is the homomorphism which preserves vertex degrees? – 2012-08-06
-
0just the 2's onto the 2's and the 1's onto the 1's – 2012-08-06
-
0Oh, I see. I didn't understand how you were mapping the vertices of degree $1$ but it is clear now. – 2012-08-06
-
0What if we add "connected" to the assumptions? – 2012-08-06
-
42-3-2 and 3-2-2, just complete with 1s where needed... – 2012-08-06