[Math] Difference between graph homomorphism and graph isomorphism

graph theory

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?

Best Answer

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
Related Question