I am still not getting how graph isomorphism and homomorphism differ.

Can anyone show me two graphs that are homomorphic, but not isomorphic?

Also, Wikipedia says that when the function and the inverse function are both homomorphic, two graphs are isomorphic. How is it?

  • 2
    $\begingroup$ A homomorphism can put one graph inside of another, bigger graph, a process which cannot be reversed without the map's restriction to the vertex sets being a set bijection. If you can understand the fact that set isomorphisms (bijections) need not be all of the set homomorphisms (arbitrary mappings), you should be able to understand the same principle for graphs (and other concrete categories, tangentially). $\endgroup$ – anon Aug 16 '12 at 8:52
  • $\begingroup$ "Two graphs are homomorphic" doesn't really make sense. $\endgroup$ – Patrick Da Silva Aug 16 '12 at 8:52
  • $\begingroup$ @anon I get it. Thanks. $\endgroup$ – Absolutio Zaka Aug 16 '12 at 8:55

A homomorphism can be from a bigger to a smaller graph. Here’s a concrete example:

                    / \  
                   /   \                        0   
                  b     c                      / \  
                  |     |                     /   \  
                  d-----e                    1-----2  
                     G                          H

The map $h:V(G)\to V(H)$ given by $h(a)=h(d)=0$, $h(b)=h(c)=1$, and $h(e)=2$ is a graph homomorphism: it sends edges $ab,db$, and $ac$ to $01$, $ce$ to $12$, and $de$ to $02$. Clearly, however, $G$ and $H$ are not isomorphic, since they don’t even have the same number of vertices.

Notice that in general if $h:G\to V$ is a graph isomorphism, then $h(u)h(v)$ is an edge of $H$ if and only if $uv$ is an edge of $G$. If $h$ is merely a graph homomorphism, however, $h(u)h(v)$ can be an edge of $H$ even if $uv$ isn’t an edge of $G$. Thus, if $K$ is the graph shown below, the map that takes $a,b,c,d$, and $e$ to $0,1,2,3$, and $4$, respectively, is a homomorphism but not an isomorphism.

                        / \  
                       /   \   
                      |     |  
  • $\begingroup$ In my book it says that two graphs are homeomorphic if and only if each can be obtained from the same graph by adding vertices (necessarily of degree 2) to edges.I don't understand how the last example of yours the map that takes a,b,c,d, and e to 0,1,2,3, and 4, respectively, is a homomorphism ?Is graph of G and K be obtained by adding vertices to H?Is that how G and K become homeormophic $\endgroup$ – clarkson Oct 10 '14 at 5:32
  • 1
    $\begingroup$ @clarkson: My answer says nothing about homeomorphic graphs; do you mean homomorphic graphs? $\endgroup$ – Brian M. Scott Oct 10 '14 at 5:39
  • $\begingroup$ Is homomorphic graphs and homeomorphic graphs two different things?I meant homeomorphic graphs which applies to Kuratowski's theorem $\endgroup$ – clarkson Oct 10 '14 at 6:35
  • $\begingroup$ @clarkson: Yes, they are different things. In my answer $G$ and $H$ are homeomorphic to each other, but neither is homeomorphic to $K$. $\endgroup$ – Brian M. Scott Oct 10 '14 at 6:41
  • $\begingroup$ Thanks for the explanation $\endgroup$ – clarkson Oct 10 '14 at 6:51

Consider the following two graphs:

  0 --- 1
                 0 --- 1
  2 --- 3
     G              H

Note that the function $f : \{ 0,1,2,3 \} \to \{ 0,1 \}$ defined by $f (0) = f(2) = 0$ and $f(2) = f(3) = 1$ is a graph homomorphism from $G$ into $H$. The only edges of $G$ are $\{0,1\}$ and $\{2,3\}$, and clearly $\{f(0),f(1)\} = \{0,1\} = \{f(2),f(3)\}$ are edges (the same edge!) of $H$.

Note that the function $g: \{ 0,1 \} \to \{ 0,1,2,3 \}$ defined by $g(0) = 0$ and $g(1) = 1$ is also a graph homomorphism from $H$ into $G$. The only edge of $H$ is $\{0,1\}$ and clearly $\{g(0),g(1)\} = \{0,1\}$ is an edge of $G$.

Therefore $G$ and $H$ are homomorphically equivalent, as defined on the Wikipedia page. In fact, $H$ is just a retract of $G$, with the function $f$ above a retraction. However they are not isomorphic, as their underlying sets have different sizes.

  • $\begingroup$ Arthur - this is related to a different post of yours. In his answer here Stephan Geschke mention your answer, which you have deleted. (I am not sure whether this is sufficient reason to undelete it - the choice is up to you - but I wanted to ping you, so that you're aware of it.) $\endgroup$ – Martin Sleziak Aug 20 '12 at 21:43
  • $\begingroup$ @Martin: Thanks, I wouldn't have known if you didn't ping me. I've expanded and undeleted that answer. $\endgroup$ – user642796 Aug 21 '12 at 3:07
  • 1
    $\begingroup$ There is a typo. The function f should be defined with f(1) = f(3) = 1. Currently it reads f(2) = f(3) = 1 instead. $\endgroup$ – davitenio Aug 27 '15 at 19:08

There seem to be different notions of structure preserving maps between graphs. It is clear that an isomorphism between graphs is a bijection between the sets of vertices that preserves both edges and non-edges.

For the following I am talking about undirected graphs without double edges or loops.

The usual notion of homomorphism is a map that preserves edges, but not necessarily non-edges. It follows that a homomorphism can map two different vertices to a single vertex if the two vertices in the domain don't form an edge. For example, the graph with two vertices and no edge can be mapped homomorphically to the graph that has only a single vertex.

Maps that preserve both edges and non-edges (in the sense that two different vertices that do not form an edge are mapped to two different vertices that do not form an edge) are just graph embeddings. They are 1-1 but not necessarily onto.

Another interesting notion of structure preserving map between graphs would be that of a modular map, a map that preserves both edges and non-edges, unless two distinct vertices are identified. Modular maps show up in modular decompositions of graphs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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