Isomorphism and Homomorphism of Graphs

Definition

A graph isomorphism between two graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$ is a bijective mapping $f: V_G \to V_H$ such that for any two vertices $u,v \in V_G$,

$$uv \in E_G \iff f(u)f(v) \in E_H.$$

If such a mapping exists, the graphs are called isomorphic, written as $G \cong H$.

A graph homomorphism from a graph $G=(V_G,E_G)$ to a graph $H=(V_H,E_H)$ is a function $f: V_G \to V_H$ such that whenever $uv \in E_G$, we also have $f(u)f(v) \in E_H$. Unlike isomorphism, a homomorphism need not be one-to-one or onto.

Main Content

1. Graph Isomorphism

Meaning and idea

• : Two graphs are isomorphic when they have the same structure, even if their vertex names, drawings, or layouts are different. Isomorphism preserves adjacency and non-adjacency completely. In other words, if one graph has an edge between two vertices, the corresponding vertices in the other graph must also have an edge, and if there is no edge, that absence must also be preserved.

Example and properties

• : Consider two triangles drawn differently. If both have three vertices and every pair of vertices is connected, then they are isomorphic. A simple example is:
• Graph $G$: vertices $\{a,b,c\}$, edges $\{ab,bc,ca\}$
• Graph $H$: vertices $\{1,2,3\}$, edges $\{12,23,31\}$

The mapping $a \mapsto 1$, $b \mapsto 2$, $c \mapsto 3$ is an isomorphism.
Important characteristics preserved under isomorphism include:

• number of vertices and edges
• degree sequence
• connectivity
• cycles of given lengths
• adjacency relations
• components and isolated vertices

A useful way to visualize isomorphic graphs is through relabeling:

G:                    H:
a --- b               1 --- 2
 \   /                 \   /
   c                     3

Both represent the same triangle structure, so $G \cong H$.

2. Graph Homomorphism

Meaning and idea

• : A graph homomorphism is a structure-preserving map, but it allows vertices of the first graph to “collapse” onto the same vertex in the second graph. This makes homomorphisms much more general than isomorphisms. The only requirement is that edges must map to edges.

Example and properties

• : Let $G$ be a path $P_3$ with vertices $u,v,w$ and edges $uv, vw$. Let $H$ be a triangle $K_3$ with vertices $1,2,3$. A map $$f(u)=1,\quad f(v)=2,\quad f(w)=1$$ is a homomorphism because:

• edge $uv$ maps to $12$, which is an edge in $H$

• edge $vw$ maps to $21$, which is also an edge in $H$

Here, two different vertices of $G$ map to the same vertex in $H$, so the map is not injective.
Key features of homomorphisms:

• they preserve adjacency, but not necessarily non-adjacency
• multiple vertices may map to one vertex
• they can be used to color graphs, compress structures, and compare graph complexity
• every isomorphism is a homomorphism, but not every homomorphism is an isomorphism

A small diagram showing collapsing under homomorphism:

G:                  H:
u --- v --- w       1 --- 2 --- 3
|                   (triangle can also be used)

If $u$ and $w$ both map to vertex $1$, the path’s edges still go to valid edges in $H$.

3. Differences, Relationships, and Special Cases

Relationship between the two concepts

• : Isomorphism is a special case of homomorphism. A graph isomorphism is a homomorphism that is both one-to-one and onto, and whose inverse is also edge-preserving. Homomorphism is therefore the broader concept, while isomorphism is the exact structural equivalence case.

Comparison and special cases

• : The distinction becomes clear in practical use:
• Isomorphism means “same graph structure.”
• Homomorphism means “structure can be mapped into another graph in a way that preserves edges.”

Some important special observations:

• A graph may have a homomorphism to a complete graph $K_n$ exactly when it is $n$-colorable.
• If two graphs are isomorphic, then they have identical structural invariants.
• If a homomorphism exists, it does not imply the graphs are the same size or equally complex.

Example:

• A 4-cycle $C_4$ can be homomorphically mapped to $K_2$ by coloring alternating vertices with the two vertices of $K_2$.
• But $C_4$ is not isomorphic to $K_2$, since they differ in number of vertices and edges.

This shows why homomorphisms are more flexible and why isomorphisms are stricter.

Working / Process

1. Check basic graph invariants first

Compare the number of vertices, number of edges, degree sequence, number of connected components, and cycle structure. If any of these differ, the graphs cannot be isomorphic. For homomorphism, check whether adjacency can be preserved under some mapping.

2. Construct a vertex mapping

Try to assign vertices of one graph to vertices of the other. For isomorphism, the map must be bijective. For homomorphism, repeated images are allowed. Then verify every edge maps to an edge.

3. Verify preservation of structure

For isomorphism, confirm both adjacency and non-adjacency are preserved in both directions. For homomorphism, only edge preservation is necessary. If every required condition holds, the mapping is valid.

Advantages / Applications

Graph comparison and recognition

• : Isomorphism helps determine whether two graphs are structurally identical, which is useful in network analysis, chemistry, and pattern matching.

Graph coloring and constraint problems

• : Homomorphisms are strongly connected to graph coloring. Mapping a graph to a complete graph gives a mathematical way to express proper colorings.

Computer science and mathematics applications

• : These concepts are used in database theory, logic, circuit design, image recognition, molecular structure comparison, and algorithmic graph theory.

Summary

• Graph isomorphism means two graphs have exactly the same structure under relabeling.
• Graph homomorphism is a more general structure-preserving map that sends edges to edges.
• Isomorphism is a special case of homomorphism with a bijective correspondence.
• These concepts help in comparing graphs, studying colorings, and analyzing structural patterns.