1
$\begingroup$

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?

  • 1
    I'm using [this](http://en.wikipedia.org/wiki/Graph_homomorphism) definition of homomorphism.2012-08-06

1 Answers 1

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...

  • 4
    2-3-2 and 3-2-2, just complete with 1s where needed...2012-08-06