Applications of Graph TheoryShariefuddin Pirzada and Ashay Dharwadker 
Abstract 

Ackowledgements 
Introduction 
Graph theory is rapidly moving into the
mainstream of mathematics mainly because of its applications in diverse
fields which include biochemistry (genomics), electrical engineering (communications
networks and coding theory), computer science (algorithms and computations)
and operations research (scheduling). The wide scope of these and other
applications has been welldocumented cf. [5] [19].
The powerful combinatorial methods found in graph theory have also been
used to prove significant and wellknown results in a variety of areas
in mathematics itself. The best known of these methods are related to a
part of graph theory called matchings, and the results from this area are
used to prove Dilworth’s chain decomposition theorem for finite partially
ordered sets. An application of matching in graph theory shows that there
is a common set of left and right coset representatives of a subgroup in
a finite group. This result played an important role in Dharwadker’s 2000
proof of the fourcolor theorem [8] [18].
The existence of matchings in certain infinite bipartite graphs played
an important role in Laczkovich’s affirmative answer to Tarski’s 1925 problem
of whether a circle is piecewise congruent to a square. The proof of the
existence of a subset of the real numbers R that is nonmeasurable
in the Lebesgue sense is due to Thomas [21]. Surprisingly,
this theorem can be proved using only discrete mathematics (bipartite graphs).
There are many such examples of applications of graph theory to other parts
of mathematics, but they remain scattered in the literature [3][16].
In this paper, we present a few selected applications of graph theory to
other parts of mathematics and to various other fields in general.

2. Fermat’s (Little) Theorem 

There are many proofs of Fermat’s Little
Theorem. The first known proof was communicated by Euler in his letter
of March 6, 1742 to Goldbach. The idea of the graph theoretic proof given
below can be found in [12] where this method,
together with some number theoretic results, was used to prove Euler’s
generalization to nonprime modulus.
2.1. Theorem (Fermat). Let a be a natural number and let p be a prime such that a is not divisible by p. Then, a^{p}  a is divisible by p. Proof. Consider the graph G = (V, E), where
the vertex set V is the set of all sequences (a_{1},
a_{2},
..., a_{p}) of natural numbers between 1 and a (inclusive),
with a_{i} ≠ a_{j}
for some i ≠ j. Clearly, V
has a^{p}  a elements. Let u = (u_{1},
u_{2},
..., u_{p}),
v = (u_{p},
u_{1},
..., u_{p}_{1})
∈V.
Then, we say uv ∈E. With
this assumption, each vertex of G is of degree 2. So, each component
of G is a cycle of length p. Therefore, the number of components
is (a^{p}  a) / p. That is, p 
(a^{p}  a). ☐


3. The NielsonSchreier Theorem 

Babai [2] proved the
NielsonSchreier Theorem for subgroups of free groups, as well as other
results in diverse areas, from his Contraction Lemma. The particular case
of this lemma when
G is a tree, and its use in proving the NielsonSchreier
Theorem, was also observed by Serre [20].
Let H be a group and let S be a set of generators of H. The product of generators and their inverses which equals the identity element 1 is called a trivial relation among the generators in S if 1 can be obtained from that product by repeatedly replacing xx^{1} or x^{1}x by 1. Otherwise such a product is called a nontrivial relation. A group H is free if H has a set of generators such that all relations among the generators are trivial. The Cayley graph G(H, S) of H with respect to S, has vertices x, y, ... ∈H, and {x, y} is an edge if and only if either x = ya or y = xa, for some a ∈S.
A group H of permutations acting on a set V is called semiregular if for each x ∈V, the stabilizer H_{x} = {h ∈H: x^{h} = x} consists of the identity only, where x^{h} denotes the image of x under h. If H is transitive and semiregular, then it is regular. For any fixed h ∈H, let h_{R} be a permutation of H obtained by multiplying all the elements of H on the right by h. The collection H_{R} = {h_{R}: h ∈H} is a regular group of permutations (under composition) and is called the (right) regular permutation representation of H. The automorphism group of a graph G is the group of all permutations p of the vertices of G with the property that {p(x), p(y)} is an edge of G if and only if {x, y} is an edge of G. It can be shown cf. [2] that G is a Cayley graph of the group H if and only if G is connected and H_{R} is a subgroup of the automorphism group of G. If G is any graph and e = {x, y} an edge of G, then by contraction along e, we mean the graph G' obtained by identifying the vertices x and y. We say that a graph G_{1} is contractible onto a graph G_{2} if there is a sequence of contractions along edges which transforms G_{1} to G_{2}. 3.1. Contraction Lemma. Let H be a semiregular subgroup of the automorphism group of a connected graph G. Then, G is contractible onto some Cayley graph of H. The proof of this lemma is rather technical, although it only uses ideas from group theory and graph theory cf. [2]. 3.2. Corollary. If J is a subgroup of a group H, then any G(H, S) is contractible onto G(J, T) for some set T of generators of J. 3.3. Theorem (NielsonSchreier). Any subgroup of a free group is free. Proof. We first show that in any group H and for any set
S
of generators of H, the Cayley graph G(H,
S)
contains a cycle of length > 2 if and only if there is a nontrivial relation
among the generators in S. To show this, suppose x_{0},
x_{1},
..., x_{n} = x_{0} is a cycle of G(H,
S).
Then, there are a_{i}∈
S, 1 ≤ i ≤
n, such that x_{i}_{1}a_{i}^{ε}i
= x_{i} where ^{ε}i∈
{1, 1}. Hence, x_{n} = x_{n}_{1}a_{n}^{ε}n
= x_{n}_{2} a_{n}_{1}^{ε}n1a_{n}^{ε}n
= ... = x_{0} a_{1}^{ε}1a_{2}^{ε}2
... a_{n}^{ε}n,
that is, the identity 1 = a_{1}^{ε}1a_{2}^{ε}2
... a_{n}^{ε}n.
If this were a trivial relation, then there would exist an integer i,
1 ≤ i ≤
n, such that a_{i} = a_{i}_{+1} and
ε_{i}
= ε_{i+1}. However, this implies
that x_{i}_{1} = x_{i}_{+1},
a contradiction. Similarly, if a_{1}^{ε}1a_{2}^{ε}2
... a_{n}^{ε}n
= 1 is a nontrivial relation, then x_{0}, x_{1},
..., x_{n}, where x_{i} = x_{i}_{1}a_{i}^{ε}i,
1 ≤ i ≤
n, and x_{0} = x_{n}, is a closed trial in
G(H,
S),
which must contain a cycle.


4. The SNP Assembly Problem 

In computational biochemistry there are
many situations where we wish to resolve conflicts between sequences in
a sample by excluding some of the sequences. Of course, exactly what constitutes
a conflict must be precisely defined in the biochemical context. We define
a conflict graph where the vertices represent the sequences in the sample
and there is an edge between two vertices if and only if there is a conflict
between the corresponding sequences. The aim is to remove the fewest possible
sequences that will eliminate all conflicts. Recall that given a simple
graph G, a vertex cover C is a subset of the vertices such
that every edge has at least one end in C. Thus, the aim is to find
a minimum vertex cover in the conflict graph G (in general, this
is known to be a
NPcomplete problem [13]).
We look at a specific example of the SNP assembly problem given in [15]
and show how to solve this problem using the vertex cover algorithm [6].
A Single Nucleotide Polymorphism (SNP, pronounced “snip”) [15] is a single base mutation in DNA. It is known that SNPs are the most common source of genetic polymorphism in the human genome (about 90% of all human DNA polymorphisms).
The SNP Assembly Problem [15] is defined as
follows. A SNP assembly is a triple (S, F, R) where
S
= {s_{1}, ..., s_{n}} is a set of
n
SNPs, F = {f_{1}, ..., f_{m}} is a
set of m fragments and R is a relation R: S×F →
{0, A, B} indicating whether a SNP s_{i} ∈S
does not occur on a fragment f_{j} ∈F
(marked by 0) or if occurring, the nonzero value of s_{i}
(A or B). Two SNPs s_{i} and s_{j}
are defined to be in conflict when there exist two fragments f_{k}
and f_{l} such that exactly three of R(s_{i},
f_{k}),
R(s_{i},
f_{l}),
R(s_{j},
f_{k}),
R(s_{j},
f_{l})
have the same nonzero value and exactly one has the opposing nonzero
value. The problem is to remove the fewest possible SNPs that will eliminate
all conflicts. The following example from [15]
is shown in the table below. Note that the relation R is only defined
for a subset of S×F obtained
from experimental values.
Note, for instance, that s_{1} and s_{5}
are in conflict because R(s_{1}, f_{2})
= B, R(s_{1}, f_{5}) = B,
R(s_{5},
f_{2})
= B, R(s_{5},
f_{5}) = A.
Again, s_{4} and s_{6} are in conflict because
R(s_{4},
f_{1})
= A, R(s_{4},
f_{3}) = A,
R(s_{6},
f_{1})
= B,
R(s_{6},
f_{3}) = A.
Similarly, all pairs of conflicting SNPs are easily determined from the
table. The conflict graph G corresponding to this SNP assembly problem
is shown below in figure 4.3.
We now use the vertex cover algorithm [6] to
find minimal vertex covers in the conflict graph G. The input is
the number of vertices 6, followed by the adjacency matrix of G
shown below in figure 4.4. The entry in row i and column j
of the adjacency matrix is 1 if the vertices s_{i} and s_{j}
have an edge in the conflict graph and 0 otherwise.
The vertex cover program [6] finds two distinct
minimum vertex covers, shown in figure 4.5.
Thus, either removing s_{1}, s_{4} or removing s_{4}, s_{5} solves the given SNP assembly problem. 

5. Computer Network Security 

A team of computer scientists led by Eric
Filiol [11] at the Virology and Cryptology Lab,
ESAT, and the French Navy, ESCANSIC, have recently used the vertex cover
algorithm
[6] to simulate the propagation of stealth
worms on large computer networks and design optimal strategies for protecting
the network against such virus attacks in realtime.
The simulation was carried out on a large internetlike virtual network and showed that that the combinatorial topology of routing may have a huge impact on the worm propagation and thus some servers play a more essential and significant role than others. The realtime capability to identify them is essential to greatly hinder worm propagation. The idea is to find a minimum vertex cover in the graph whose vertices are the routing servers and whose edges are the (possibly dynamic) connections between routing servers. This is an optimal solution for worm propagation and an optimal solution for designing the network defense strategy. Figure 5.1 above shows a simple computer network and a corresponding minimum vertex cover {2, 4, 5}. 

6. The Timetabling Problem 

In a college there are m professors
x_{1},
x_{2},
…, x_{m} and
n subjects y_{1},
y_{2},
…, y_{n} to be taught. Given that professor x_{i}
is required (and able) to teach subject
y_{j} for p_{ij}
periods (p = [ p_{ij
}] is called the teaching
requirement matrix), the college administration wishes to make a timetable
using the minimum possible number of periods. This is known as the timetabling
problem [4] and can be solved using the following
strategy. Construct a bipartite multigraph G with vertices x_{1},
x_{2},
…, x_{m},
y_{1}, y_{2}, …,
y_{n}
such that vertices x_{i} and y_{j} are connected
by p_{ij} edges. We presume that in any one period each
professor can teach at most one subject and that each subject can be taught
by at most one professor. Consider, first, a single period. The timetable
for this single period corresponds to a matching in the graph and, conversely,
each matching corresponds to a possible assignment of professors to subjects
taught during this period. Thus, the solution to the timetabling problem
consists of partitioning the edges of G into the minimum number
of matchings. Equivalently, we must properly color the edges of G
with the minimum number of colors. We shall show yet another way of solving
the problem using the vertex coloring algorithm
[7].
Recall that the line graph L(G) of
G has as vertices
the edges of G and two vertices in L(G) are connected
by an edge if and only if the corresponding edges in G have a vertex
in common. The line graph L(G) is a simple graph and a proper
vertex coloring of L(G) yields a proper edge coloring of
G
using the same number of colors. Thus, to solve the timetabling problem,
it suffices to find a minimum proper vertex coloring of L(G)
using [7]. We demonstrate the solution with a
small example.
Suppose there are four professors x_{1}, x_{2}, x_{3}, x_{4} and five subjects y_{1}, y_{2}, y_{3}, y_{4}, y_{5} to be taught [4]. The teaching requirement matrix p = [ p_{ij }] is given below in figure 6.1.
We first construct the bipartite multigraph G shown below in
figure 6.2.
Next, we construct the line graph L(G). The adjacency
matrix of L(G) is given below.
Now, we use the vertex coloring algorithm [7]
to find a minimum proper 4coloring of the vertices of L(G).
Vertex Coloring: (1, green), (2, red), (3, blue), (4, yellow),
(5, yellow), (6, green), (7, green), (8, yellow), (9, red), (10, blue),
(11, yellow). This, in turn, yields a minimum proper edge 4coloring of
the bipartite multigraph G:
Edge Coloring: ({x_{1}, y_{1}},
green), ({x_{1}, y_{1}}, red), ({x_{1},
y_{3}},
blue), ({x_{1}, y_{4}}, yellow), ({x_{2},
y_{2}},
yellow), ({x_{2}, y_{4}}, green), ({x_{3},
y_{2}},
green), ({x_{3},
y_{3}}, yellow), ({x_{3},
y_{4}},
red), ({x_{4},
y_{4}}, blue), ({x_{4},
y_{5}},
yellow). Interpret the colors green, red, blue, yellow as periods 1, 2,
3, 4 respectively. Then, from the edge coloring of G, we obtain
a solution of the given timetabling problem as shown below in figure 6.5.


7. Map Coloring and GSM Mobile Phone Networks 

Given a map drawn on the plane or the
surface of a sphere, the famous four color theorem asserts that it is always
possible to properly color the regions of the map such that no two adjacent
regions are assigned the same color, using at most four distinct colors
[8][18][1].
For any given map, we can construct its dual graph as follows. Put a vertex
inside each region of the map and connect two distinct vertices by an edge
if and only if their respective regions share a whole segment of their
boundaries in common. Then, a proper vertex coloring of the dual graph
yields a proper coloring of the regions of the original map.
We use the vertex coloring algorithm [7] to
find a proper coloring of the map of India with four colors, see figures
7.1 and 7.2 above.


8. Knight’s Tours 

In 840 A.D., alAdli [17],
a renowned shatranj (chess) player of Baghdad is said to have discovered
the first reentrant knight's tour, a sequence of moves that takes the
knight to each square on an 8×8 chessboard
exactly once, returning to the original square. Many other reentrant knight's
tours were subsequently discovered but Euler [10]
was the first mathematician to do a systematic analysis in 1766, not only
for the 8×8 chessboard, but for reentrant
knight's tours on the general n×n
chessboard. Given an n×n
chessboard, define a knight's graph with a vertex corresponding to each
square of the chessboard and an edge connecting vertex i with vertex
j
if and only if there is a legal knight's move from the square corresponding
to vertex i to the square corresponding to vertex
j. Thus,
a reentrant knight's tour on the chessboard corresponds to a Hamiltonian
circuit in the knight's graph. The Hamiltonian circuit algorithm [9][13]
has been used to find reentrant knights tours on chessboards of various
dimensions.


References 





JOURNAL OF THE KOREAN SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS VOL. 11 NO. 4 2007 