Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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). –  anon Aug 16 '12 at 8:52
    
"Two graphs are homomorphic" doesn't really make sense. –  Patrick Da Silva Aug 16 '12 at 8:52
    
@anon I get it. Thanks. –  Absolutio Zaka Aug 16 '12 at 8:55
add comment

3 Answers 3

up vote 10 down vote accepted

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

                         0  
                        / \  
                       /   \   
                      1-----2  
                      |     |  
                      3-----4  
                         K
share|improve this answer
add comment

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.

share|improve this answer
    
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.) –  Martin Sleziak Aug 20 '12 at 21:43
    
@Martin: Thanks, I wouldn't have known if you didn't ping me. I've expanded and undeleted that answer. –  Arthur Fischer Aug 21 '12 at 3:07
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.