Difference between graph homomorphism and graph isomorphism

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?

Solution 1:

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

                     a  
                    / \  
                   /   \                        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:V(G)\to V(H)$ 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.

                         0  
                        / \  
                       /   \   
                      1-----2  
                      |     |  
                      3-----4  
                         K

Solution 2:

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.

Solution 3:

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.