Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I 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? – Qiaochu Yuan Aug 6 '12 at 17:06
I'm using this definition of homomorphism. – user02138 Aug 6 '12 at 17:21

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

share|cite|improve this answer
Sorry, what is the homomorphism which preserves vertex degrees? – Qiaochu Yuan Aug 6 '12 at 17:07
just the 2's onto the 2's and the 1's onto the 1's – Xoff Aug 6 '12 at 17:10
Oh, I see. I didn't understand how you were mapping the vertices of degree $1$ but it is clear now. – Qiaochu Yuan Aug 6 '12 at 17:12
What if we add "connected" to the assumptions? – user02138 Aug 6 '12 at 17:13
2-3-2 and 3-2-2, just complete with 1s where needed... – Xoff Aug 6 '12 at 17:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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