arXiv:1610.05725v2 [] 27 Oct 2016

Polynomial-time algorithm for determining the
graph isomorphism
Anatoly D. Plotnikov
e-mail: a.plotnikov@list.ru
Abstract
We develop the methodology of positioning graph vertices relative
to each other to solve the problem of determining isomorphism of two
undirected graphs. Based on the position of the vertex in one of the
graphs, it is determined the corresponding vertex in the other graph.
For the selected vertex of the undirected graph, we define the neighborhoods of the vertices. Next, we construct the auxiliary directed
graph, spawned by the selected vertex. The vertices of the digraph
are positioned by special characteristics — vectors, which locate each
vertex of the digraph relative the found neighborhoods.
This enabled to develop the algorithm for determining graph isomorphism, the runing time of which is equal to O(n4 ).

MCS2000: 05C85, 68Q17.
Key words: isomorphism, algorithm, graph, graph isomorphism problem.

1

Introduction

Let Ln is the set of all n-vertex undirected graphs without loops and multiple
edges.
Let, further, there is a graph G = (V, E) ∈ Ln , where V = {v1 , v2 , . . . , vn }
is the set of graph vertices and E = {e1 , e2 , . . . , em } is the set of graph
edges. Local degree deg(v) of a vertex v ∈ VG is the number of edges which
incident to the vertex v. Every graph G ∈ Ln can be characterized by the
vector DG = (deg(vi1 ), deg(vi2 ), . . . , deg(vin )) of local vertex degrees, where
deg(vi ) ≤ deg(vj ), if i < j.
1

The graphs G = (VG , EG ), H = (VH , EH ) ∈ Ln is called isomorphic if
between their vertices there exists a one-to-one (bijective) correspondence
ϕ : VG ↔ VH such that if eG = {v, u} ∈ EG then the corresponding edge
eH = {ϕ(v), ϕ(u)} ∈ EH , and conversely [3]. The graph isomorphic problem
consists in determining isomorphism graphs G, H ∈ Ln .
The problem of determining the isomorphism of two given undirected
graphs is used to solve chemical problems, and to optimize programs. Effective (polynomial-time) algorithms for solving this problem were found for
some narrow classes of graphs [1, 2]. However for the general case, effective
methods for determining the isomorphism of graphs are not known.
The purpose of this article is to propose a polynomial-time algorithm for
determining isomorphism of the connected undirected graphs.

2

Algorithm bases

We develop the methodology of positioning graph vertices relative to each
other to solve the problem of determining isomorphism of two undirected
graphs. Based on the position of the vertex in one of the graphs, it is determined the corresponding vertex in the other graph.
Consider the elements of our algorithm.
Let there be a graph G ∈ Ln . For the vertex v ∈ V of the graph G we
define the concept of neighborhood of kth level (0 ≤ k ≤ n − 1).
The neighborhood of 1st level of the vertex v is the set of all graph vertices
that are adjacent to the vertex v. In general, a neighborhood of k-th level is
the set of all graph vertices that are adjacent to the vertices (k − 1)th level.
(k)
Such a neighborhood we denote NG (v). For convenience, we assume that
the vertex V forms a neighborhood of the zero level.
For the given vertex v by means of the graph G we construct an auxiliary
~
directed graph G(v),
spawned by the vertex v ∈ V , as follows.
The set of vertices belonging to one and the same neighborhood of the
vertex v, form a line of graph vertices. Each line has the same number as
the level of a neighborhood of the vertex v. Further, if in the initial graph G
the edge {v, u} connects a vertex v belonging to lines with a lower number
than vertex u then such an edge to replace by the arc (v, u), outgoing from
a vertex v and incoming to the vertex u. If the edge of the graph connects
vertices of one and the same line, this edge is replaced by two opposite arcs.
Fig. 1 presents the graph G = (V, E) ∈ Ln and the auxiliary di~ 1 ), spawned according to this graph by the vertex v1 ∈ V 1 . Here
graph G(v
1

The graph G is borrowed from [3]

2

✉
✑◗
✑
✓❙ ◗
✑
✑ ✓ ❙ ◗◗
❙ ◗✉ v5
✑
✉
PP ✓
❙ ✁
PP
❆ ✓
PP
❆✓
PP❙✁
❆
✁P
❙✉ v6
✉
✓
❍❍❆
✁
❅ ❍
❅❆ ❍❍ ✁
❆✉ ❍✁✉
❅
v4

v3

v2

v7

v1

G

✉
❇❇❅
✂✂❅
✂ ❇ ❅
❇ ❅ ☞
✂
✎
✂ v5 ❇✉ ❅✉ v7
✉
✉
❏❏ v3 ❏❏ ✡✡
✡✡
❏
❏✡
✡
❏ ✡❏ ✡
❏✉
❏✉
✡
✡
v1

v2

v4

v6
~ 1)
G(v

~ 1)
Figure 1: Graph G and auxiliary digraph G(v
.
(0)

NG (v1 ) = {v1 } is its own neighborhood (line) of the 0th level of the vertex
(1)
v1 , the set of vertices NG (v1 ) = {v2 , v3 , v6 , v7 } forms a neighborhood (line)
(2)
of 1st level and, finally, the set NG (v1 ) = {v3 , v6 } is a neighborhood of the
2nd level of the vertex v1 .
~
Each vertex v of the auxiliary digraph G(v),
we will characterize by two
vectors Iv and Ov .
Elements of vectors Iv and Ov are numbers. These numbers are the line
numbers of vertices of the auxiliary digraph. Vector Iv contains the line
numbers of vertices, from which arcs of the digraph come into the vertex
v, and the vector Ov contains the line numbers of vertices that receive arcs
from vertex v. If several arcs income into the vertex v from one and the same
line of digraph then the line number is repeated in the vector accordingly.
Similarly, if several arcs from the vertex v come into one and the same line,
this number is also repeated in the vector accordingly. The elements of the
vectors Iv and Ov assume ordered in ascending order of value of numbers.
The vectors Iv and Ov will be called the characteristics of the vertex v,
and Iv is input and Ov is output characteristics. Characteristics of the two
vertices v1 , v2 are equal, if their input and output characteristics are equal,
respectively, i.e., if Iv1 = Iv2 and Ov1 = Ov2 .
~ 1 ), shown
Find characteristics of the vertices of the auxiliary digraph G(v
in Fig. 1.
Iv1 = ⊘;
Ov1 = (1, 1, 1, 1);
Iv5 = (0, 1);
Ov5 = (1, 2, 2);

Iv2 = (0, 1, 1);
Ov2 = (1, 1, 2);
Iv6 = (1, 1, 1, 2);
Ov6 = (2);

Iv3 = (0, 1);
IV4 = (1, 1, 1, 2);
Ov3 = (1, 2, 2); Ov4 = (2);
Iv7 = (0, 1, 1);
Ov7 = (1, 1, 2).

~
~
Auxiliary digraphs G(v)
and H(u)
is called positionally equivalent if the
lines of graphs of the same level have the equal number of vertices, respec3

tively, having equal characteristics.
In general, the positionally equivalent digraphs have arcs connecting the
vertices of the same level. This introduces an element of equivocation, i.e. in
this case, we can not say that the positionally equivalent digraphs determine
isomorphic graphs G and H.
~
A vertex v ∈ VG is called unique in digraph G(v)
if doesn’t exist other
vertex with the characteristics equal to characteristics of the vertex v.
It is easy to see that the vertex v1 is the unique vertex of the constructed
digraph (see Fig. 1).
Theorem 1 Let the graphs G and H are isomorphic. Let, further, the auxil~
~
iary digraphs G(v)
and H(u)
are the positionally equivalent, and each digraph
has an unique vertex vi ∈ VG and uj ∈ VH such that Ivi = Iuj , Ovi = Ouj .
Then between the vertices of digraphs there exists a bijective correspondence
ϕ such that uj = ϕ(vi ).
Proof. Let the conditions of Theorem 1 are satisfied. As the graphs G
and H are isomorphic then between vertices of positionally equivalent di~
~
graphs G(v)
and H(u),
having equal characteristics, there is a bijective correspondence ϕ. Since the vertices vi and uj have the same unique positioning
~
~
in the digraphs G(v)
and H(u)
then the relation uj = ϕ(vi ) is performed in
any correspondence ϕ. In particular, that sort unique vertices are always
vertices which spawn the positionally equivalent auxiliary digraphs.♦.
Note that in general case, the vertices of graphs G and H having the same
local degree, spawn different auxiliary digraphs.
Theorem 2 Suppose there are two isomorphic graph G = (VG , EG ), H =
(VH , EH ) ∈ Ln . Suppose, further, for the subgraph G1 ⊆ G, induced by the
~ 1 (x) has constructed. Then
vertex set X ⊆ VG , the auxiliary directed graph G
in the graph H there exists a subgraph H1 ⊆ H, spawned by the set of vertices
~ 1 (y) is positionally equivalent to
Y ⊆ VH , such that its auxiliary digraph H
~ 1 (x).
the digraph G
Proof. The validity of the above statement follows from the definition of
isomorphism of graphs, and the same sequence of construction of any of the
auxiliary digraphs.♦.

4

3

Algorithm

Using the results of the previous section, we can propose several algorithms
for determining the isomorphism of two given graphs G, H ∈ Ln . The simplest of them is as follows.
To determine the fact of isomorphism of graphs G and H, we look for
equally positioned vertex graphs.
Find the vertices v ∈ VG and u ∈ VH having positionally equivalent
auxiliary digraphs in the graphs G and H. Remove the found vertices from
the graphs together with the incident edges and repeat the process until we
have exhausted the list of vertices of graphs. If at some point in the graphs G
and H cannot find a pair of vertices having positionally equivalent auxiliary
digraphs, then stop the calculation, since the graphs are not isomorphic.
We describe the proposed algorithm in more detail.
Input of the algorithm: graphs G = (VG , EG ), H = (VH , EH ) ∈ Ln ,
isomorphism of which must be determined, if it exists. We believe that these
graphs have the same number of vertices and edges, as well as their vectors
of local degrees DG and DH are equal.
Output of the algorithm: conclusion about the isomorphism of graphs G
and H.
Algorithm for determining isomorphism graphs.
Step 1. Put Q = G, S = H, N := n, i := 1, j := 1.
Step 2. Choose a vertex vi ∈ VQ in the graph Q.
~ i ) using the graph Q.
Step 3. Construct the auxiliary digraph Q(v
~ i ).
Step 4. Find the characteristics of vertices of the auxiliary graph Q(v
Step 5. Choose the vertex uj ∈ VS in the graph S.
~ j ) using the graph S.
Step 6. Construct the auxiliary digraph S(u
~ j ).
Step 7. Find the characteristics of vertices of the auxiliary graph S(u
~ i ) and
Step 8. Compare the characteristics of the vertices of a digraphs Q(v
~ j ) in the neighborhoods of the vertices vi and uj of the same level.
S(u
~ i ) and S(u
~ j ) are positionally equivalent then put
Step 9. If the digraphs Q(v
VQ := VQ \ {vi }, VS := VS \ {uj }, N := N − 1. Go to Step 11.
Step 10. If j ≤ N then put j := j + 1 and go to Step 5. Otherwise finish the
calculations as the graphs G and H are not isomorphic.
Step 11. If i ≤ N then put i := i + 1, j := 1 and go to Step 2. Otherwise,
stop the calculations. The graphs G and H are isomorphic.

5

Theorem 3 The algorithm for determining the graph isomorphism determines an isomorphism of the given graph if it exists.
Proof. The Theorem 1 is established that if graphs G and H are isomorphic then the pair of unique vertices v and u that spawn positionally
~
~
equivalent digraphs G(v)
and H(u)
belong to some bijective mapping ϕ of
the vertices of this graph. Therefore, removal of vertices v and u of graphs G
and H together with incident edges, leads to the construction of subgraphs
of G′ ⊂ G and H ′ ⊂ H which is also isomorphic. Therefore, the repetition of the above procedure will lead to the exhaustion of the list of vertices
isomorphic graphs G and H.
Now suppose that the graphs G and H are not isomorphic and the vertex
~
~
v ∈ VG , u ∈ VH spawn positionally equivalent digraphs G(v)
and H(u).
Then, obviously, in these digraphs there exist some subsets of vertices X ⊂
VG and Y ⊂ VH , having corresponding equal characteristics, which spawn
different (non-isomorphic) subgraphs. Here v ∈ (VG \ X), u ∈ (VH \ Y ) and
Card(X) = Card(Y ).
Removing sequentially from graph Q and S vertices, spawning the equivalent auxiliary digraphs, we obtain non-isomorphic subgraphs. As a result,
the algorithm terminates without possibility finding a pair of vertices with
equivalent digraphs.♦
Unfortunately, the collection of pairs of vertices, determined by the proposed algorithm, as a whole, does not always determine the bijective mapping
of the vertices in initial isomorphic graphs. This is the price for the simplicity
of the algorithm.
Theorem 4 The running time of the algorithm for determining the graph
isomorphism equal to O(n4 ).
Proof. We determine the running time of the algorithm in steps 5–10.
Steps 5, 10 need to spend one time unit at each step.
Steps 6–8 require to spend O(n2 ) time units each.
Steps 9 require to spend O(n) time units.
Therefore, n-multiple executing steps 5–10 requires to spend O(n3 ) time
units.
Executing Steps 2–10 one times requires to spend O(n3 ) time units and
executing n times requires O(n4 ) time units.♦

4

Conclusion

We have developed the efficient (polynomial-time) algorithms for determining
isomorphism of undirected graphs. With that end in view, we used the
6

methodology of positioning vertices concerning the selected vertex and its
neighborhoods as the input and output characteristics of vertices. It allowed
effectively to compare the structure of the given graphs.
Apparently, ideology of the positioning of vertices, developed in this
study, can be used in solving the problem of finding a subgraph which is
isomorphic to the given graph. Although in this case we should expect origin
of essential search.

References
[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of
computer algorithms. Addison-Wesley publishing company, N.Y., 1976.
[2] M.R. Garey and D.S. Johnson.
Computers and Intractability.
W.H.Freeman and Company, San Francisco, 1979.
[3] D. B. West. Introduction to Graph Theory, 2nd ed. Prentice Hall, Inc.,
NJ, 2001.

7

Appendix
We illustrate the work of the proposed algorithm with an example.
Let two graph G, H ∈ Ln are given, for which it is necessary to determine
the isomorphism (see Fig. 2).
u2

v2

v1

✉
✡✂✂❇❏
✡ ❇❏
✡✂ ❇❏
❇ ❏
✡ ✂
❇✉ ❏
✂
✡ ✉
✁u❅
✡ u❆4
❅
5 ❏
❆ ✁
✡
❅❏
✁❳
❆✉
❳
✡ ✘✘✘✘
❏
❳
u6
❳❅
❳❅
✡✘
✉
✘
❏✉
❳

v3

✉
PP
✏✉
✏✏ ❅
P
✏
P
PP ❅
✏✏
PP
✏✏
❅
P
✉
✏
✏✉v
PP
✏✏ 4
❅ PP
✏
PP✏✏
❅
✏ PP
✏✏
P✉
❅✉

v6

G

v5

u1

H

u3

Figure 2: Initial graphs G and H.
The given graphs have an equal number of vertices, edges and vectors of
degrees.
Choose a vertex v1 in the graph G and construct the auxiliary digraph
~ 1 ) (see Fig. 3).
G(v
v1

v2

✉
✂❇❅
✂ ❇❅
✂
❇ ❅ ☞
✎
✂
❇❇✉ ❅
✂✉
✉
❅✉v6
❇
❅
✂✂ v5
❅ v3❇
❅ ❇ ✂
❅❇ ✂
v❅
4 ❇✂✉

u1

u2

~ 1)
G(v

✉
✂❇❅
✂ ❇❅
✂
❇ ☞
❅
✎
✂
❇❇✉u4 ❅
✂✉
✉
❅✉u6
❇❇
❅
✌
✂✂
❅ u3 ✍
❅ ❇ ✂
❅❇ ✂
u❅
5❇✂✉

~ 1)
H(u
~ 1 ) and H(u
~ 1 ).
Figure 3: Auxiliary digraphs G(v

Calculated characteristics of vertices of the constructed digraph. The
results bring to the table.
Iv1 = ⊘;
Ov1 = (1, 1, 1, 1);
Iv4 = (1, 1, 1, 1);
Ov4 = ⊘;

Iv2 = (0, 1, 1);
Ov2 = (1, 1, 2);
Iv5 = (0, 1, 1);
Ov5 = (1, 1, 2);
8

Iv3 = (0, 1, 1);
Ov3 = (1, 1, 2);
Iv6 = (0, 1, 1);
Ov6 = (1, 1, 2);

~ 1)
Choose a vertex u1 in the graph H and build an auxiliary digraph H(u
(see Fig. 3).
The calculated characteristics of vertices of the newly constructed digraph. The results bring to the table.
Iu1 = ⊘;
Ou1 = (1, 1, 1, 1);
Iu4 = (0, 1, 1);
Ou4 = (1, 1, 2);

Iu2 = (0, 1, 1);
Ou2 = (1, 1, 2);
Iu5 = (1, 1, 1, 1);
Ou5 = ⊘;

Iu3 = (0, 1, 1);
Ou3 = (1, 1, 2);
Iu6 = (0, 1, 1);
Ou6 = (1, 1, 2);

~ 1 ) and
It is easy to see that the constructed auxiliary directed graph G(v
~ 1 ) positionally equivalent.
H(u
Vertices v1 and u1 are removed from the initial graphs G and H respectively. We obtain graphs G1 and H1 (see Fig. 4).
u2

v2

✉
❇❏
✂✂❇❏
✂ ❇❏
❇ ❏
✂
✉
❇✉ ❏
✂
✁u❅
❅
u❆4
5 ❏
❆ ✁
❅❏
✁❳
❆✉
❳
❅❏
❳
u6
❳❳❅
❏✉
❳

v3

✉
✉
PP
❅
PP
PP ❅
PP
❅
P
✏✉v
✏✏ 4
✏
✏
✏✏
✉
✏✏
✉

v6

G1

v5

H1

u3

Figure 4: Subgraphs G1 and H1 .
In the subgraph G1 , choose a vertex v2 and build an auxiliary digraph
~ 1 (v2 ) (see Fig. 5).
G
~ 1 (v2 ).
We calculate the characteristics of vertices of the auxiliary digraph G

Iv2 = ⊘;
Ov2 = (1, 1, 1);
Iv5 = (1, 1, 1);
Ov5 = ⊘;

Iv3 = (0, 1); Iv4 = (0, 1, 1);
Ov3 = (1, 2); Ov4 = (1, 1, 2);
Iv6 = (0, 1);
Ov6 = (1, 2);

In the subgraph of H1 , choose a vertex u2 and build an auxiliary digraph
~ 1 (u2 ) (see Fig. 5).
H
~ 1 (u2).
Calculate characteristics of vertices of the auxiliary digraph H
9

u2

v2

v3

✉
✡✡❏❏
✡
❏
✡
❏
✉
✡
✉v4 ❏✉v6
❏
✡
❏
✡
❏
✡
❏❏✉
✡
v
✡ 5

u3

✉
✡✡❏❏
✡
❏
✡
❏ ☞
✎
✉
✡
✉
❏✉u5
❏
u4 ✡
❏
✡
❏
✡
❏❏✉
✡✡u6

~ 1 (u2 )
H

~ 1 (v2 )
G

~ 1 (v2 ) and H
~ 1 (u2 ).
Figure 5: Auxiliary digraphs G
Iu2 = ⊘;
Ou2 = (1, 1, 1);
Iu5 = (0, 1, 1);
Ou5 = (1, 1, 2);

Iu3 = (0, 1);
Iu4 = (0, 1);
Ou3 = (1, 2);
Ou4 = (1, 2);
Iu6 = (1, 1, 1);
Ou6 = ⊘;

~ 2 ) and H(u
~ 2)
Again we find that the constructed auxiliary digraphs G(v
are positionally equivalent.
Vertices v2 and u2 are removed from the subgraphs G1 and H1 , respectively. We obtain subgraphs G2 and H2 (see Fig. 6).
v3

✉
❅
❅
❅
✏✉v
✏✏ 4
✏
✏
✏✏
✉
✏✏
✉

v6

G2

✉
✉
✁
❆
❅
u4
u❅
5
❆ ✁
❅
✁❳❳
❆✉
❳
u6
❳❅
❳❅
❳✉

v5

H2

u3

Figure 6: Subgraphs G2 and H2 .
~ 2 (v3 )
In the graph G2 , choose a vertex v3 and build an auxiliary digraph G
(see Fig. 7).
~ 2 (v3 ).
Calculate characteristics of vertices of the auxiliary digraph G
Iv3 = ⊘;
Iv4 = (0, 1); Iv5 = (0, 1); Iv6 = (1, 1);
Ov3 = (1, 1); Ov4 = (1, 2); Ov5 = (1, 2); Ov6 = ⊘;
~ 2 (u3 ) and find the characteristics
Construct an auxiliary directed graph H
of its vertices.
10

v3

u3

✉
✡✡❏❏
❏
✡
❏
✡
❏✉v5
✉
✡
✡
❏
✡
❏
✡
❏
v6❏❏✉✡✡

v4

u5

~ 2 (v3 )
G

✉
✡✡❏❏
❏
✡
❏
✡
✉
❏✉u6
✡
✡
❏
✡
❏
✡
❏
u4❏❏✡
✉✡

~ 2 (u3)
H

~ 2 (v3 ) and H
~ 2 (u3 ).
Figure 7: Auxiliary digraphs G
Iu3 = ⊘;
Iu4 = (1, 1); Iu5 = (0, 1); Iu6 = (0, 1);
Ou3 = (1, 1); Ou4 = ⊘;
Ou5 = (1, 2); Ou6 = (1, 2);
~ 2 (v3 ) and H
~ 2 (u3 ) are positionally equivalent.
Auxiliary digraphs G
Vertices v3 and u3 are removed from the graph G2 and H2 respectively.
We obtain graphs G3 and H3 (see Fig. 8).
✉

u❆4

✏✉v4
✏✏
✏
✏
✏✏
✏
✉✏
✉

v6

G3

❆ ✁
✁
❆✉

✉
✁u5

u6

v5

H3

Figure 8: Subgraphs G3 and H3 .
~ 3 (v4 )
In the graph G3 , choose a vertex v4 and build an auxiliary digraph G
(see Fig. 9).
v4

v5

u4

✉
✡✡❏❏
❏
✡
❏
✡
✉
❏✉v6
✡

u5

G3 (v4 )

✉
✡✡❏❏
❏
✡
❏
✡
✉
❏✉u6
✡

H3 (u4 )

~ 3 (v4 ) and H
~ 3 (u4 ).
Figure 9: Auxiliary digraphs G
~ 3 (v4 ).
We calculate the characteristics of the auxiliary graph G
Iv4 = ⊘;
Iv5 = (0, 1); Iv6 = (0, 1);
Ov4 = (1, 1); Ov5 = (1);
Ov6 = (1);
11

~
Construct an auxiliary digraph doesh
3 (u4 ) and find the characteristics of
its vertices.
Iu4 = ⊘;
Iu5 = (0, 1); Iu6 = (0, 1);
Ou4 = (1, 1); Ou5 = (1);
Ou6 = (1);
~ 4 ) and H(u
~ 4)
Again we find that the constructed auxiliary digraphs G(v
are positionally equivalent.
Vertex v4 and u4 are removed from the graph G3 and doesh3 respectively.
We obtain subgrapgs G4 and H4 (see Fig. 10).
v5 ✉

✉v6

u5 ✉

✉u6

G4

H4

Figure 10: Subgraphs G4 and H4 .
In the graph of G4 , choose a vertex v5 and build an auxiliary digraph
~ 4 (v5 ) (see Fig. 11).
G
v5

u5

✉

✉

v6 ✉
G4 (v5 )

u6 ✉
H4 (u5 )

~ 4 (v5 ) and H
~ 4 (u5 ).
Figure 11: Auxiliary digraphs G
~ 4 (v5 ).
We calculate the characteristics of the auxiliary graph G
Iv5 = ⊘;
Iv6 = (0);
Ov5 = (1); Ov6 = ⊘.
~ 4 (u5) (see Fig. 11) and find the characConstruct an auxiliary digraph H
teristics of its vertices.
Iu5 = ⊘;
Iu6 = (0);
Ou5 = (1); Ou6 = ⊘;

12

~ 4 (v5 ) and H
~ 4 (u5 ) are positionally equivWe find that auxiliary digraphs G
alent.
Vertices v5 and u5 are removed from the subgraphs G4 and H4 , respectively. We obtain one-vertex subgraphs G5 and H5 . Auxiliary digraphs
~ 5 (v6 ) and H
~ 5 (u6 ) contain one vertex and,of course, are the positionally
G
equivalent.
Conclusion: the given graphs G and H are isomorphic.

13

