Introductory topics in graph theory

K. V. Iyer, Ph.D.
Dept. of Computer Science and Engg.
National Institute of Technology
Trichy - 620 015
August 2010
For third year B.Tech. students for the core course
3:0 Combinatorics and Graph Theory

First draft
1
Graph theory K. V. Iyer
Contents
1 Introduction 4
2 Basic denitions and ideas 5
2.1 Types of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The degree sum formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Some operations on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Representations of graphs 10
4 Connectivity of graphs 13
4.1 Vertex cuts, edge cuts and connectivity . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Vertex connectivity and edge-connectivity . . . . . . . . . . . . . . . . . . . . . . . 14
5 Trees and their properties 17
5.1 Denition and characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Sum of distances from a leaf of a tree . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Spanning Tree 21
6.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7 Coloring of graphs 23
7.1 Motivation and denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.2 Bounds for (G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
April 2007 2 CSE/NIT
Graph theory K. V. Iyer
Graph a diagram that shows relationships between numbers.
Article in Microsoft Encarta Reference Library 2003.
Note 0.1:
These notes are intended for the B.E. students of the rst course on Combinatorics and Graph
Theory. By no means, these are original! Much of the material is drawn from contemporary
sources, mainly older books; therefore, at the moment I am not looking for a publisher. I have
added acknowledgements in the form of references. Errors are likely to be present herein - typos
and others - students should point out these. No rewards please.
Note 0.2:
Concepts in graphs are introduced starting from denitions of various types of graphs. Isomor-
phism, degree-sum formula, graph operations, graph representations are given. Connectivity
denitions and related results, trees their properties and spanning trees are mentioned. Coloring
of graphs is introduced and bounds on (G) is given in the form of Brooks theorem.
April 2007 3 CSE/NIT
Graph theory K. V. Iyer
1 Introduction
Broadly speaking, graph theory is concerned with the properties between a given set of objects
with some structure, usually not obvious. Informally, a graph is a set of objects called vertices (or
points or nodes) connected by links or lines called edges. A graph is usually depicted by means
of a diagram in the plane in which the vertices are denoted by points in the plane and edges by
lines joining certain pairs of vertices. This idea of graphs is well-known in Mathematics and in
Computer Science although the representation and depiction of graphs is a separate notion. Graph
theory has its origins in recreational mathematics and its use as a tool to solve practical problems.
Since 1930 graph theory has received considerable attention as a mathematical discipline. This
is due to its wide range of applications in many elds like computer science, operations research,
organic chemistry and networks. For example applications of graph theory to other areas of
mathematics see Ref. [?]. In recent times, the study of graph theory has seen a phenomenal
growth in view of its wide-range connections to theoretical issues in Computer Science.
The earliest known recorded result in graph theory, now called the Konigsberg problem is due
to the Swiss mathematician Leonhard Euler in 1736. In 1859 W. R. Hamilton discovered the idea
of a cycle that visits each vertex of a graph exactly once. Trees are special kinds of connected
graphs that contain no cycles. In 1847 Kirchho rst used trees in his work on electrical networks.
It is also known that Arthur Caley used trees systematically in his attempts to enumerate the
isomers of the saturated hydrocarbons.
Traditional graph theory requires only little mathematical preparation except for combinato-
rial arguments and martix theory as evident by the inuential books of the 1970s. Some classical
graph theory problems include obtaining Eulerian and Hamiltonian walks, ows and connectivity,
matching, planarity, coloring, stable and dominating sets. Not all these problems have ecient
algorithmic solutions (Computer science theory suggests that ecient solutions are unlikely to ex-
ist). Modern books on the subject additionally deal with extremal graph theory, Ramsey theory,
random graphs as well as graph minors. As in number theory, many problems in graph theory
April 2007 4 CSE/NIT
Graph theory K. V. Iyer
are easy to pose and understand although their solutions may require research eort. Perhaps
the most famous one is the Four Color Theorem (FCT) which states that every planar map
can be colored using not more than four colors so that regions sharing a common boundary are
colored dierently. FCT had the status of a conjecture in 1852 when it was rst posed by Francis
Guthrie. A rst of its kind, the nal proof of the FCT given by Kenneth Appel and Wolfgang
Haken in 1976 required 1200 hours of computer time.
2 Basic denitions and ideas
2.1 Types of graphs
A graph G consists of a vertex set V (G) = {v
1
, . . . , v
n
} and an edge set E(G) = {e
1
, . . . , e
m
},
where each edge consists of an unordered pair of vertices. If e is an edge of G then it is denoted
by uv (which is the same as vu). V (G) and E(G) are abbreviated to V and E respectively. We
call u and v, the endpoints or endvertices of e. Given an edge e = uv we say u and v are adjacent.
Similarly two edges e
1
and e
2
having a common endpoint are said to be adjacent. A loop is an
edge whose endpoints are the same. Parallel edges or multiple edges are edges that have the same
pair of endpoints. A simple graph is one that has no loops and no multiple edges. The order n
of a graph G is the number of vertices in V . A graph of order 1 is called trivial. The size m of a
graph G is the number of edges in E. A graph is nite if it has nite order.
It is possible to assign a direction or orientation to each edge in a graphwe then treat an
edge e (with endpoints u and v) as an ordered pair (u, v) denoted by

uv; this edge is dierent
from (v, u) or

vu. A directed graph or a digraph G consists of a vertex set V = {v
1
, . . . , v
n
}
and an edge set E = {e
1
, . . . , e
m
} where each (directed) edge is an ordered pair of vertices. In
depicting a digraph, we assign a direction marked by an arrow to each edge. Thus an edge

uv of
a digraph will be a line from u to v with an arrow in the direction from u to v.
Figures ?? and ?? show some examples of graphs and digraphs. G
1
is a graph where the set
of vertices {1,2,3} forms one component and the set of vertices {4,5} forms another component.
We thus have a graph that is not connected. The connected components of such a graph may be
studied separately. G
2
is an example digraph. Consider the graphs G
3
and G
4
. We can make
April 2007 5 CSE/NIT
Graph theory K. V. Iyer
the following correspondence (denoted by the double arrow ) between V (G
3
) and V (G
4
):
1 a, 2 b, 3 d, 4 d
5 e, 6 f, 7 g, 8 h
Letting i, j {1, 2, 3, 4, 5, 6, 7, 8} and x, y {a, b, c, d, e, f, g, h} we can easily check that if i x
and j y then ij E(G
3
) if and only if xy E(G
4
). In other words, G
3
and G
4
are the
same graph. More formally, two simple graphs G and H are isomorphic if there is a bijection
: V (G) V (H) such that the following condition is satised: u
a
u
b
E(G) if and only if
v
a
v
b
E(H) where u
a
, u
b
are any two vertices in V (G) and (u
a
) = v
a
and (u
b
) = v
b
.
Examples:
1. The Petersen graph is isomorphic to the following graph Q: The vertex set V (Q) is the set
of unordered pairs of numbers (i, j), i = j, 1 i, j 5. Two vertices {i, j} and {k, l}
(i, j, k, l {1, 2, . . . , 5}) form an edge if and only if {i, j} {k, l} = .
2. Let V be a set cardinality n (vertices). From V we can obtain
_
n
2
_
unordered pairs (possible
edges). Each subset of these ordered pairs denes a simple graph and hence there are 2
(
n
2
)
simple graphs with vertex set V . If |V | = 4, then there are 64 simple graphs on four vertices.
However, there are only 11 dierent ones upto isomorphism. (see Fig ??).
***** gure out the gure *****
Consider the pairs G
i
and G
12i
in Fig ??. We see that G
12i
is obtained from G
i
by
removing its edge(s) and introducing all edges not in G
i
. This is the idea of complementation of
a graph. Note that G
6
is isomorphic to its complement. While there are only 11 non-isomorphic
simple graphs on six vertices, there are as many as 1044 non-isomorphic simple graphs on seven
vertices! When the order and the size of graphs are small (small graphs), it is easy to check
for isomorphism by exhaustive enumeration. However, the problem of deciding whether two
given graphs are isomorphic or not is dicult in general and it has been a subject of research in
Computer Science.
April 2007 6 CSE/NIT
Graph theory K. V. Iyer
The complement

G of a simple graph G is the simple graph with vertex set V (

G) = V (G)
and edge set E(

G) dened thus: uv E(

G) if and only if uv / E(G). That is, E(

G) =
{uv|uv / E(G)}. A simple graph is called self-complementary if it is isomorphic to its own
complement. The complement of the null graph N
n
is a graph with n vertices in which every
distinct pair of vertices is an edge. Such a graph is called a complete graph or a clique. The
complete graph on n vertices is denoted by K
n
. With n vertices all the possible
1
2
n(n 1) edges
are present in E(K
n
).
A subgraph of a graph G is a graph H such that V (H) V (G) and E(H) E(G). In nota-
tion, we write H G and say that H is a subgraph of G. For S V (G), the induced subgraph
G[S] or < S > of G is a subgraph H of G such that V (H) = S and E(H) contains all edges of
G whose endpoints are in S (see Fig ??). Note that a complete graph may have many subgraphs
that are not cliques but every induced subgraphs of a complete graph is a clique. The components
of a graph G are its maximal connected subgraphs.
***** Figure : induced subgraph *****
An independent set of a graph G is a vertex subset S V (G) such that no two vertices of S
are adjacent in G. It is easy to check that a clique of G is an independent set of

G and vice versa.
We next introduce a special class of graphs called bipartite graphs. A graph G is called
bipartite if V (G) can be partitioned into two subsets X and Y such that each edge of G has one
endpoint in X and the other in Y . We express this as G = G(X, Y ). A complete bipartite graph
G is a bipartite graph G(X, Y ) whose edge set consists of all possible pairs of vertices having one
endpoint in X and the other in Y . If X has m vertices and Y has n vertices such a graph is
denoted by K
m,n
. Note that K
m,n
is isomorphic to K
n,m
. It is easy to see that K
m,n
has mn
edges. A trail of length n in a graph G (digraph G) is a sequence of vertices v
1
, v
n
, where each
v
i
is a vertex of G, such that for 0 i n 1, v
i
v
i+1
is an edge (oriented edge) of G. A trail
is said to be closed if v
1
= v
n
. When all the vertices in the sequence are distinct, the trail is
referred to as a path. Thus a graph G is connected if there is a path from vertex x to vertex y for
every vertex pair x, y. A closed trail where the only two identical vertices are v
1
and v
n
is called
a cycle.
April 2007 7 CSE/NIT
Graph theory K. V. Iyer
The party problem:
The party problem says: There are six people at a party. Then, there are three people who are
mutual friends or there are three people who are mutual strangers.
Graph theory solves the problem easily. Consider the complete graph K
6
. We associate
the six people with the six vertices of K
6
. We color the edges joining two vertices black if the
corresponding people know each other. If two people do not know each other, we color the edge
joining the corresponding vertices grey. If there are three people who know (dont know) each
other, then we should have a black (grey) triangle in K
6
.
Given an assignment of colors to all edges of K
6
, call a subgraph H monochromatic if all its
edges have the same color. The party problem can now be posed as:
If we arbitrarily color the edges of K
6
black or grey, then there must be a monochromatic
clique on three vertices.
Let u, v, w, x, y, z be the vertices of K
6
. An arbitrary vertex, say u in K
6
has degree 5. So
when we color the edges incident with u, we must use the color black or grey at least three times.
Without loss of generality, assume that the three edges are colored black as shown in Fig. ??.
Let these edges be uv, ux and uw. If any one of the edges vw, vx or xw is now colored black, we
get the required black triangle. Hence we suppose all these edges are colored grey. But then this
gives a grey triangle.
2.2 The degree sum formula
Let v be a vertex in G. The degree d(v) or d
G
(v) of v is the number of edges of G incident with
v. A vertex of degree 1 in a graph G is called a leaf or pendant of G. We denote the maximum
degree in a graph G by (G) or ; the minimum degree is denoted by (G) or . A graph is
regular if = . In other words a graph is k-regular if = = k. A k-regular graph with n
vertices has nk/2 edges. The complete graph K
n
is (n1) regular. The complete bipartite graph
K
n,n
is n-regular. The Petersen graph is 3-regular. A 3-regular simple connected graph is called
a cubic graph. Cubic graphs on n vertices exist for even values of n. Note that K
3,3
is a cubic
graph.
April 2007 8 CSE/NIT
Graph theory K. V. Iyer
Theorem 2.1:
For any graph G

v V (G)
d(v) = 2m.
Proof. When the degrees of all the vertices are summed up, each edge is counted twice. Hence
the result.
By the degree-sum formula, the average vertex degree is 2m/n. So 2m/n . A
vertex of a graph is odd or even depending on whether its degree is odd or even.
Corollary 2.2:
In any graph G, there is an even number of odd vertices.
Proof. Let A and B be respectively the set of odd and even vertices of G. Then for each u B,
d(u) is even and so

uB
d(u) is also even. By the degree-sum formula

uB
d(u) +

wA
d(w) =

vV (G)
d(v) = 2m.
This gives

wA
d(w) = 2m

uB
d(v) which is even.
2.3 Some operations on graphs
Let G = (V, E) be a graph. We dene graph operations that lead to new graphs from G.
(a) Edge addition: Let u, v V . Then G+uv is the graph
_
V, E {uv}
_
.
(b) Edge deletion: Let e E. Then Ge is the graph
_
V (G), E \ {e}
_
.
(c) Vertex deletion: Let v V . Then Gv is the graph
_
V \{v}, {e E|e not incident with v}
_
.
The operation deletes the vertex v and all edges incident on v.
(d) Edge subdivision: The graph G % e is
_
V {z},
_
E \ xy
_

_
xz, zy
_
_
,
where e = xy E and z / V is a new vertex; we insert a new vertex z on the edge xy.
April 2007 9 CSE/NIT
Graph theory K. V. Iyer
(e) Deletion of a set of vertices: Let W V . The graph G\ W is the graph obtained from G by
deleting all the vertices of W as also each edge that has at least one vertex in W.
(f) Cartesian product: Let G
1
= (V
1
, E
1
) and G
1
= (V
1
, E
1
) be two simple graphs. Then
their Cartesian product G
1
G
2
or G
2
G
2
is dened thus: let V
1
= {v
1
, , v
k
} and
V
2
= {u
1
, , u
m
}. The vertex set of G
1
G
2
is V
1
V
2
and the vertices are accordingly
labeled < v
i
, u
j
>. Two such vertices < v
i
, u
j
> and < v
q
, u
r
> are connected if
(i) v
i
= v
q
and u
j
u
r
E
2
or (ii) u
j
= u
r
and v
i
v
q
E
1
.
(g) Closure of G: Let the order of G be n. If there are no two nonadjacent vertices u and v
in G with d(u) + d(v) > n then its closure is G. Otherwise we nd such a pair and form
H = G + uv; taking G as H, we repeat the process till we do not nd such a pair. The
resultant graph is the closure of the original G.
More to explore:
(a) The notion of edge subdivision is useful in dening homeomorphic equivalence of two graphs
in the traditional sense.
(b) For two graphs G
1
and G
2
their products can be also be dened in other ways.
3 Representations of graphs
A graph G = (V , E) can be represented as a set of adjacency lists or as an adjacency matrix. For
sparse graphs where |E| is much less compared to |V |
2
, the adjacency adjacency list representation
is preferred. For dense graphs for which |E| is close to |V |
2
, the adjacency matrix representation
may be good. The adjacency list representation of G consists of an array Adj of |V |. For each
vertex u of G, Adj[u] points to the list of all vertices v that are adjacent to u. For a directed
graph Adj[u] points to the list of all vertices v such that

uv is an edge of G. It is easy to see that
the adjacency list representation of a graph (directed or undirected) has the desirable property
that the amount of memory it requires is
O(max(|V |, |E|)) = O(|V | +|E|).
Given an adjacency list representation of a graph, to determine if an edge uv is present in the
graph, the only way is to search the list Adj[u] for v. The process of determining the presence
April 2007 10 CSE/NIT
Graph theory K. V. Iyer
(or absence) of an edge uv is simpler in the following representation of a graph.
To represent a graph G = (V, E), we rst number the vertices of G as 1, , |V | in an arbitrary
manner. The adjacency matrix of G is then the matrix A = (a
ij
) where
a
ij
=
_

_
1 if ij E(G).
0 otherwise.
The above denition applies to directed graphs also where we specify the elements a
ij
as
a
ij
=
_

_
1 if

ij A(G).
0 otherwise.
A graph may have many adjacency lists and adjacency matrices because the numbering of the
vertices is arbitrary. All the representations yield graphs that are isomorphic and therefore it
hardly matters in writing programs. It is then possible to study properties of graphs that do not
dependent on the labels of the vertices.
Theorem 3.1:
Let G be a graph with n vertices v
1
, . . . , v
n
. Let A represent the corresponding adjacency matrix
of G. Let A
k
be the result of multiplication of k (a positive integer) copies of A. Then the (i, j)
th
entry of A
k
is the number of dierent (v
i
, v
j
)-walks in G of length k.
Proof. We prove the result by induction on k. For k = 1, the theorem follows from the denition
of the adjacency matrix of G, since a walk of length 1 from v
i
to v
j
is just the edge v
i
v
j
. We
now assume that the result is true for A
k1
for k > 1. Let A
k1
= (b
ij
) i.e., b
ij
is the number of
dierent walks of length k 1 from v
i
to v
j
. Let A
k
= (c
ij
). It is required to prove that c
ij
is
the number of dierent walks of length k from v
i
to v
j
. By denition A
k
= A
k1
A and by the
denition of matrix multiplication
c
ij
=
n

r=1
_
(i, r)
th
element ofA
k1
_

_
(r, j)
th
element of A
_
=
n

r=1
b
ir
a
rj
.
Now every (v
i
, v
j
)-walk of length k consists of a (v
i
, v
r
)-walk of length k1 for some r followed by
the edge v
r
v
j
. Now a
rj
= 1 or 0 according as v
r
is adjacent to v
j
or not. By induction hypothesis
April 2007 11 CSE/NIT
Graph theory K. V. Iyer
the number of (v
i
, v
r
)-walks of length k 1 is the (i, r)
th
entry b
ir
of matrix A
k1
. Hence the
total number of (v
i
, v
j
)-walks of length k is
n

r=1
b
ir
a
rj
= c
ij
.
Hence the result is true for A
k
as well.
The next theorem uses the above result to determine whether or not a graph is connected.
Theorem 3.2:
Let G be a graph with n vertices v
1
, . . . , v
n
and let A be the adjacency matrix of G. Let B = (b
ij
)
be the matrix given by
B = A+A
2
+. . . +A
n1
.
G is connected if and only if for every pair of distinct indices i, j, b
ij
= 0; that is, G is connected
if and only if all the elements o the main diagonal in B are nonzero.
Proof. Let a
(k)
ij
denote the (i, j)
th
entry of A
k
for k = 1. . . . , n 1. We then have
b
ij
= a
(1)
ij
+a
(2)
ij
+. . . +a
(n1)
ij
.
By Theorem ??, a
(k)
ij
denotes the number of distinct walks of length k from v
i
to v
j
. Thus
b
ij
= number of dierent (v
i
, v
j
)-walks of length 1 +
number of dierent (v
i
, v
j
)-walks of length 2 +

+ number of dierent (v
i
, v
j
)-walks of length n 1.
That is b
ij
gives the number of dierent (v
i
, v
j
)-walks of length less than n. Assume that G is
connected. Then for every pair i, j (i = j) there is a path from v
i
to v
j
. Since G has only n
vertices any path is of length at most n 1. Hence there is a path of length less than n from v
i
to v
j
. This implies b
ij
= 0. Conversely, assume that b
ij
= 0 for every pair i, j (i = j). Then from
the above discussion it follows that there is at least one walk of length less than n from v
i
to v
j
.
This holds for every pair i, j (i = j). Therefore we conclude that G is connected.
April 2007 12 CSE/NIT
Graph theory K. V. Iyer
4 Connectivity of graphs
4.1 Vertex cuts, edge cuts and connectivity
In a connected graph G, a subset V

V of is a vertex cut of G if GV

is disconnected. It is a
k-vertex cut if |V

| = k. V

is called a separating set of vertices of G. A vertex v of a connected

graph G is a cut vertex of G if {v} is a vertex cut of G.
Let G be a nontrivial graph. Let S be a proper nonempty subset of V . Let [S,

S] denote the
set of all edges of G having one endpoint in S and the other in

S. A set of edges of G of the form
[S,

S] is called an edge cut of G. An edge e E is a cut edge of G if {e} is an edge cut of G. An
edge cut of cardinality k is called a k-edge cut of G. If e is a cut edge of a connected graph, then
Ge has exactly two components.
***** vertex cut, edge cut gures *****
The characterization of cut vertex and cut edge follow from the following theorems.
Theorem 4.1:
A vertex v of a connected graph G with at least three vertices is a cut vertex of G if and only if
there exist vertices u and w of G, distinct from v, such that v is in every (u, w)-path in G.
Proof. If v is a cut vertex G, then Gv is disconnected. Let G
1
and G
2
be the two components
of G \ v. Choose u, w such that u V (G
1
) and w V (G
2
). Then every (u, w)-path in G must
contain v as otherwise u and w would belong to the same component of Gv.
Conversely, assume that the condition of the theorem holds. Then the deletion of v splits
every (u, w)-path in G and hence u and w lie in dierent components of G v. So G v is
disconnected and therefore v is a cut vertex of G.
Theorem 4.2:
In a connected graph G, an edge e = uv is a cut edge of G if and only if e does not belong to any
cycle of G.
Proof. Let e = uv be a cut edge of G and let [S,

S] = {e} be the partition of V dened by Ge
so that u S and v

S. If e belongs to a cycle of G then [S,

S] must contain at least one more
edge contradicting that {e} = [S,

S]. Hence e cannot belong to a cycle.
Conversely assume that e is not a cut edge of G. Then G e is connected and hence there
April 2007 13 CSE/NIT
Graph theory K. V. Iyer
exists a (u, v)-path P in Ge. Then P together with the edge e forms a cycle in G.
Theorem 4.3:
In a connected graph G, an edge e = uv is a cut edge i there exist vertices x and y such that e
belongs to every (x, y)-path in G.
Proof. Let e = uv be a cut edge in G. Then G e has two components, say G
1
and G
2
. Let
x V (G
1
) and y V (G
2
). Then there is no (x, y)-path in G e. Hence every (x, y)-path in G
must contain e.
Conversely, assume that there exist vertices u and v satisfying the condition of the theorem.
Then there exists no (x, y)-path in Ge and this means that Ge is disconnected. Hence e is
a cut edge of G
4.2 Vertex connectivity and edge-connectivity
Vertex and edge connectivity may be viewed as two parameters which in some sense measure
the connectedness of a graph. Let G be a nontrivial connected graph having at least a pair of
non-adjacent vertices. The minimum k for which there exists a k-vertex cut is called the vertex
connectivity or simply the connectivity of G; it is denoted by (G). If G has no pair of nonadjacent
vertices, that is if G is a complete graph of order n, then (G) is dened to be n 1. Removal of
any set of n 1 vertices of K
n
results in a K
1
. The edge connectivity of a connected graph G is
the smallest k for which there exists a k-edge cut (i.e., an edge cut containing k edges). The edge
connectivity of G is denoted by (G). Conversely, if (G) is the edge connectivity of a graph G,
then there exists a set of (G) edges whose deletion results in a disconnected graph and no subset
of edges in G of size less than (G) has this property. Thus we have the denitions: A graph G is
r-connected if (G) r. G is r-edge connected if (G) r. An inequality involving (G), (G)
and (G) is given by the following theorem.
Theorem 4.4:
For a connected graph G
(G) (G) (G).
Proof. By denition (G) and (G), (G) 1, 1 and (G) 1. Let E be an edge cut of
April 2007 14 CSE/NIT
Graph theory K. V. Iyer
G with (G) edges and let uv E. For each edge of E that does not have both u and v as
endpoints, remove an endpoint that is dierent from u and v. If there are t such edges, at most t
vertices would have been removed. If the resulting graph is disconnected, then (G) t (G).
Otherwise, there will remain a subset of edges of E having u and v as end vertices, the removal
of which will disconnect the graph. Hence additional removal of one of u or v will disconnect the
graph or a trivial graph will result. In the process, a set of at most t + 1 vertices would have
been removed and so (G) t + 1 (G). Finally it is clear that (G) (G); in fact, if v is
a vertex of G with d
G
(v) = (G), then the set of (G) edges incident with v forms the edge cut
[{v}, V \ {v}] of G. Thus (G) (G).
Two paths from a vertex u to another vertex v (u = v) are internally disjoint if they have no
common vertex except the vertices u and v. The following theorem due to Whitney characterizes
2-connected graphs.
Theorem 4.5:
A graph G with at least three vertices is 2-connected if and only if there exists a pair of internally
disjoint paths between any pair of distinct vertices.
Proof. For any two distinct vertices u, v in G, assume that G has at least two internally disjoint
(u, v)-paths. Let w be any vertex of G. Then w is not a cut vertex of G. If not, by Theorem 4.5,
there exist vertices u and v of G such that every (u, v)-path in G contains w. Hence w is not a cut
vertex of G and therefore G is 2-connected. Conversely, assume that G is 2-connected. We apply
induction on d(u, v) to prove that G has two internally-disjoint (u, v)-paths. When d(u, v) = 1,
the graph G uv is connected, since (G) (G) 2. Any (u, v)-path in G uv is internally
disjoint in G from the (u, v)-path consisting of the edge uv. Thus u and v are connected by
two internally-disjoint paths in G. Now we apply induction on d(u, v). Let d(u, v) = k > 1 and
assume that G has internally-disjoint (x, y)-paths whenever 1 d(x, y) < k. Let w be the vertex
appearing before v on a shortest (u, v)-path. Since d(u, w) = k 1, by induction hypothesis, G
has two internally disjoint (u, w)-paths, say P and Q. (see Fig. ??).
insert gure
Since Gw is connected, a (u, v)-path, say R, must exist in Gw. If R avoids P or Q, we are
done; otherwise let z be the last vertex of R belonging to P Q. (see Fig ??). Without loss of
generality, assume that z P. We combine the (u, z)-subpath of P (with (z, v)-section of R) to
April 2007 15 CSE/NIT
Graph theory K. V. Iyer
obtain a (u, v)-path internally-disjoint from the (u, v)-path Q (w, v)-path in G.
Lemma 4.6 (Expansion Lemma):
Let G be a k-connected graph and let G

be obtained from G by adding a new vertex x and

making it adjacent to at least k vertices of G. Then G

is also k-connected.
Proof. Let S be a separating set of G

. We have to show that |S| k. If x S, then S \ {x}

separates G and so |S {x}| k. Hence |S| k + 1. If x / S, then if S separates G, then
|S| k. Otherwise, S does not separate G but separates G

and so the neighbor set of x in G

is contained in S.
Theorem 4.7:
For a graph G with |V | 3, the following conditions characterize 2-connected graphs and are all
equivalent.
(a) G is connected and has no cut vertex.
(b) For all u, v V , u = v, there are two internally disjoint (u, v)-paths.
(c) For all u, v V , u = v, there is a cycle through u and v
(d) (G) 2 and every pair of edges in G lies on a common cycle.
Proof. Equivalence of (a) and (b) follows from Theorem 4.5. Any cycle containing vertices u and
v corresponds to a pair of internally disjoint (u, v)-paths. Therefore (b) and (c) are equivalent.
Next we shall prove that (d) (c). Let x, y V be any two vertices in G. We consider edges
of the type ux and uy (since (G) > 1) or ux and wy. By (d) these edges lie on a common cycle
and hence x and y lie on a common cycle (see Fig. ??).
*****insert gure *****
Therefore (d) (c).
For proving (c) (d), suppose that G is 2-connected and let uv, xy E. We add to G, the
vertices w with neighborhood {u, v} and z with neighborhood {x, y}. By the expansion lemma,
the the resulting graph G

is 2-connected and hence w, z lie on a common cycle C in G

. Since
w, z each have degree 2, this cycle contains the paths u, w, v and x, z, y but not uv and xy. We
April 2007 16 CSE/NIT
Graph theory K. V. Iyer
replace the paths u, w, v and x, z, y in C by the edges uv and xy to obtain a desired cycle in
G.
Denition 4.8:
A graph G is nonseparable if it is nontrivial, connected and has no cut vertices. A block of a
graph is a maximal nonseparable subgraph of G.
Note that if G has no cut vertices then G itself is a block. A graph G is shown in Fig ??.(a)
and Fig ??.(b) shows its blocks B
1
, B
2
, B
3
and B
4
.
Illustr. of blocks gure
Let G be a connected graph with |V | > 2. The following statements are true:
(i) Each block of G with at least three vertices is a 2-connected subgraph of G.
(ii) Each edge of G belongs to one of its blocks and hence G is the union of its blocks.
(iii) Any two blocks of G have at most one vertex in common; such a vertex, if it exists, is a cut
vertex of G.
(iv) A vertex of G that is not a cut vertex belongs to exactly one of its blocks.
(v) A vertex of G is a cut vertex of G if and only if it belongs to at least two blocks of G.
5 Trees and their properties
5.1 Denition and characterization
A tree is a connected graph that has no cycle (equivalently, acyclic). A forest is an acyclic graph
or a collection of trees. The graphs of Fig ?? show all unlabeled trees with at most ve vertices.
The following theorem characterizes trees in dierent ways [5].
Theorem 5.1:
Given a graph G = (V, E), the following conditions are equivalent:
(i) G is a tree.
(ii) Given any two vertices, there exists a unique path between them.
April 2007 17 CSE/NIT
Graph theory K. V. Iyer
(iii) G is connected and every edge of G is a cut edge.
(iv) G is acyclic and a graph of the form G+e where e joins a pair of nonadjacent vertices of G
has a unique cycle.
(v) G is connected and |E| = |V | 1.
We begin with two lemmas.
Lemma 5.2:
Any tree with at least two vertices contains at least two leaves.
Proof. Given a tree T = (V, E), let P = (v
0
, e
1
, v
1
, . . . , e
k
, v
k
) be a longest path of T. Clearly,
length of P is at least 1 and so v
0
= v
k
. We claim that both v
0
and v
t
are leaves. This is done by
contradiction. If v
0
is not a leaf, then there exists an edge e = v
0
v where e = e
1
. Then either v is
in P or v is not in P: if v is in P (that is, v = v
i
, i 2) then the edge e together with the section
of the path P from v
0
to v
i
forms a cycle in T, a contradiction to the fact that T is acyclic. If v
is not in P, then that would contradict the choice of P.
Lemma 5.3:
Let v be a leaf in a graph G. Then G is a tree if and only if Gv is a tree.
Proof. We rst assume that G is a tree. Let x, y be two vertices of Gv. Since G is connected x
and y are connected by a path in G. This path contains only two vertices, viz., x and y, of degree
1; so it does not contain v. Consequently it is completely contained in Gv and hence Gv is
connected. As G is acyclic, Gv is also acyclic and so it is a tree.
We now assume that G v is a tree. As v is a leaf, there exists an edge uv incident on it.
Clearly, u (Gv) and (Gv) {uv} has no cycle. As Gv is connected (because it is a tree),
(Gv) {uv} = G is connected.
We now prove Theorem 5.1.
Proof of Theorem 5.1. We prove that each of the statements (ii) through (v) is equivalent to
statement (i). The proofs go by induction on the number of vertices of G, using Lemma 5.3. For
April 2007 18 CSE/NIT
Graph theory K. V. Iyer
the induction basis, we observe that all the statements (i) through (v) are valid if G contains a
single vertex only.
We rst show that (i) implies all of (ii) to (v). Let G be a tree with at least two vertices and
let v be a leaf and let v

be the vertex adjacent to v in G. By the induction hypothesis, we assume

that G v satises (ii) to (v). Now the validity of (ii), (iii) and (v) for G is obvious. For (iv),
since G is connected, any two vertices x, y V is connected by a path P and if xy / E(G), then
P +xy creates a cycle. Therefore (i) implies (iv) as well.
We now prove that each of the conditions (ii) to (v) implies (i). In (ii) and (iii) we already
assume connectedness. Also, a graph satisfying (ii) or (iii) cannot contain a cycle: for (ii), this
is because two vertices in a cycle are connected by two distinct paths and for (iii), the reason is
that by omitting an edge in a cycle we obtain a connected graph. Thus (ii) implies (i) and (iii)
also implies (i).
To verify that (iv) implies (i), it suces to check that G is connected. If x, y V , then either
xy E or the graph G+xy contains a unique cycle. Necessarily, as G is a cyclic, this cycle must
contain the edge xy. Now removal of the edge xy from this cycle give a path from x to y in G.
Thus G is connected. We nally prove that (v) implies (i). Let G be a connected graph satisfying
|V | = |E| + 1 2. The sum of the degrees of all vertices is 2|V (G)| 2. This means that not all
vertices can have degree 2 or more. Since all degrees are at least 1 (by connectedness) there exists
a vertex v of degree exactly 1, that is, a leaf of G. The graph G

= Gv is again connected and

it satises |V (G

)| = |E(G

)| + 1. Hence it is a tree by the induction hypothesis and thus G is a

tree as well.
5.2 Sum of distances from a leaf of a tree
Let G be a graph and let u, v be a pair of vertices connected in a path in G. Then the distance
from u to v, denoted by d
G
(u, v) or simply d(u, v), is the least length (in terms of the number of
edges) of a (u, v)-path in G. If G has no (u, v)-path, we dene d(u, v) = .
The diameter diam(G) of a connected graph G is dened as the maximum of the distances
between pairs of vertices of G. In symbols, diam(G) = max
u,vV
d(u, v).
Since in a tree any two vertices are connected by a unique path, the diameter of a tree T is
the length of a longest path in T.
We next prove a theorem that gives a bound on the sum of the distances of all the vertices of
April 2007 19 CSE/NIT
Graph theory K. V. Iyer
a tree T from a given vertex of T.
Theorem 5.4:
Let u be a vertex of a tree T with n vertices. Then,

vV (G)
d(u, v)
_
n
2
_
.
Proof. The proof goes by induction on the number of vertices of G. The result holds trivially for
n = 2. Let n > 2. The graph T u is a forest with components T
1
, . . . , T
k
, where k > 1. As T
is connected, u has a neighbor in each T
i
; also, since T has no cycles, u has exactly one neighbor
say v
i
, in each T
i
(the situation is shown in Fig. ??) If v V (T
i
), then the unique (u, v)-path in
T passes through v
i
and we have
d
T
(u, v) = 1 +d
T
i
(v
i
, v).
Letting n
i
= |T
i
|, we obtain

vV (T
i
)
d
T
(u, v) = n
i
+

vV (T
i
)
d
T
i
(v
i
, v).
By induction hypothesis

vV (T
i
)
d
T
i
(v
i
, v)
_
n
i
2
_
.
if we now sum the formula for distances from u over all the components of T u, we obtain (as
k

i=1
n
i
= n 1)

vV (T)
d
T
(u, v) (n 1) +

i
_
n
i
2
_
.
We note that
k

i=1
_
n
i
2
_

_
n1
2
_
since

n
i
= n 1, and the right hand side counts the edges in
K
n1
and the left hand side counts the edges in a subgraph of K
n1
(a disjoint union of cliques).
Hence we have,

v V (T)
d
T
(u, v) (n 1) +
_
n 1
2
_
=
_
n
2
_
.
April 2007 20 CSE/NIT
Graph theory K. V. Iyer
6 Spanning Tree
6.1 Denitions
We now introduce the notion of a spanning tree.
Denition 6.1:
A spanning subgraph of a graph G is a subgraph H of G such that V (H) = V (G). A spanning
tree of G is a spanning subgraph of G which is a tree.
It is not dicult to show that every connected graph has a spanning tree. Note that not every
spanning subgraph is connected and a connected subgraph of G need not be a spanning subgraph.
By labeling the vertices of K
4
, we can easily see that it has 16 dierent spanning trees (see
Fig. ??). However, K
4
has only two non-isomorphic unlabeled spanning trees namely K
1,3
and
P
4
. We state a general theorem due to the English mathematician Arthur Caley without proof.
Theorem 6.2 (A. Caley (1889)):
The complete graph K
n
has n
n2
dierent labeled spanning trees.
Corollary 6.3 (to Theorem 5.4):
If u is a vertex of a connected graph G of order n then

v V (G)
d(u, v)
_
n
2
_
.
Proof. Let T be a spanning tree of G. Every (u, v)-path in T also appears in G (G may have other
(u, v)-paths that are shorter than those in T). Therefore d
G
(u, v) d
T
(u, v), for every vertex v.
This implies

v V (G)
d
G
(u, v)

v V (G)
d
T
(u, v).
But Theorem 5.4, we have

v V (G)
d
T
(u, v)
_
n
2
_
. Hence

v V (G)
d
G
(u, v)
_
n
2
_
.
The sum of the distances over all pairs of distinct vertices a graph G is known as the total
distance or Wiener Index of G, denoted by W(G). Thus W(G) =

u,vV (G)
d(u, v).
Chemical molecules can be modeled as graphs by treating the atoms as vertices and the
atomic bonds as edges. Wiener index was originally introduced by Harold Wiener who observed
April 2007 21 CSE/NIT
Graph theory K. V. Iyer
correlation between this index and the boiling point of parans. Consider the path P
n
of n
vertices labeled 1 through n wherein vertex i to connected to vertex i 1 (1 < i n). It is easy
to see that
W(P
n
) = W(P
n1
) +
n(n 1)
2
yielding W(P
n
) =
_
n+1
3
_
.
Algorithm SP-TREE
Let G = (V, E) be the given graph, where |V (G)| = n and |E(G)| = m. Let (e
1
, e
2
, . . . , e
m
) be the
edge sequence of G labeled in some way. We now successively construct the subsets E
0
, E
1
, . . . of
G.
Set E
0
= . From E
i1
, E
i
is obtained as follows:
E
i
=
_

_
E
i1
{e
i
}, if the graph (V (G), E
i1
{e
i
}) has no cycle.
E
i1
, otherwise.
We stop if E
i
has already n 1 edges or if i = m (i.e., all edges have been considered).
The proof that algorithm SP-TREE is correct follows.
If algorithm SP-TREE outputs a graph T with n 1 edges, then T is a spanning tree of G.
If T has k < (n 1) edges, then G is a disconnected graph with n k components.
Proof. From the way the sets E
i
are constructed the graph T contains no cycle. If k = |E(T)| =
n 1, then by Theorem 5.1 (v), T is a tree and hence it is a spanning tree. If k < n 1, then T
is a disconnected graph whose every component is a tree. It is easy to reason that it has n k
components.
We prove that the vertex sets of the components of the graph T coincide with those of the
components of the graph G. Assume the contrary and let x and y be vertices lying in the same
component of G but in distinct components of T. Let C be the component of T containing the
vertex x. Consider some path,
(x = x
0
, e
1
, x
1
, e
2
, . . . , e
k
, x
k
= y)
from x to y in G as shown in Fig. ??. Let i be last index for which x
i
is contained in the component
C. Obviously i < k and have x
i+1
/ C. The edge e = x
i
x
i+1
thus does not belong to T and so
April 2007 22 CSE/NIT
Graph theory K. V. Iyer
it had to form a cycle with some edges already selected into T at some stage of the algorithm.
Therefore the graph T +e also contains a cycle; but this is impossible as e connects two distinct
components of T. This gives the desired contradiction.
7 Coloring of graphs
7.1 Motivation and denition
The vertex coloring problem is posed thus: we are asked to color (label) the vertices of a graph
G so that no two adjacent vertices receive the same color. The problem becomes interesting in
nding the minimum number of colors to be used.
Motivation - frequency allocation
Given a graph G = (V, E) the problem is to nd a map f : V C such that f(u) = f(v)
whenever uv is an edge of G. Our interest is in nding an f whose range is the minimum. The
elements of C are referred to as the colors. The minimum number of colors required is denoted
by (G) the chromatic number of G. Equivalently, the chromatic number (G) of a graph G
is the minimum number of independent subsets that partition the vertex set of G. Any such
minimum partition is called a chromatic partition of V (G). Since each color class of a graph G
is an independent set, we can see that, (G) |V (G)|/(G), where (G) is the independence
number of G.
Scheduling problems often involve permitting a number of pairwise restrictions on the jobs
that can be carried out simultaneously. A problem of this type is to schedule classes in a college.
The constraints are (a) two courses taught by the same faculty member cannot be scheduled in the
same time slot and (b) two courses meant for the same group of students should not conict. The
problem of determining the minimum number of time slots required subject to the constraints is
a graph coloring problem. The time slots are colors for the vertices, the vertices are courses, and
the edges between courses are restrictions that force dierent time slots. Another application of
vertex coloring concerns the problem of register allocation. The problem is to assign variables to
a limited number of hardware registers during the execution of a program code. This is required
in every compiler does. The idea is to use as many variables in registers as possible for quick
execution of a program. Usually, there are far more variables than registers so it is necessary to
assign multiple variables to registers. Variables conict with each other if one is used both before
April 2007 23 CSE/NIT
Graph theory K. V. Iyer
and after the other within a short period of time (for instance, within a subroutine). The goal is
to assign variables that do not conict so as to minimize the use of non-register memory. This
problem can be posed as a graph coloring problem.
Edge coloring can be eciently reduced to vertex coloring by constructing the line graph of
the input graph.
A k-coloring of a graph G is a labeling f: V (G) {1, . . . , k}. The labels are interpreted as
colors; all vertices with the same color form a color class. A k-coloring f is proper if an edge uv
is in E(G) i f(u) = f(v). A graph G is k-colorable if it has a proper k-coloring. We will call
the labels colors because their numerical value is not important. Note that (G) is then the
minimum number of colors needed for a proper coloring of G. We also say G is k-chromatic to
mean (G) = k. It is obvious that (K
n
) = n. Further (G) = 2 if and only if G is bipartite
having at least one edge. We can also reason that (C
n
) = 2 if n is even and (C
n
) = 3 if n is
odd. The Petersen graph, P has chromatic number 3. Fig. ?? shows a proper 3-coloring of P
using three colors. Certainly, P is not 2-colorable, since it contains an odd cycle.
Denition: A graph G is called critical if for every proper subgraph H of G, we have
(H) < (G). Also, G is called k-critical if it is k-chromatic and critical.
The above denition holds for any graph. When G is connected it is equivalent to the condition
that (G e) < (G) for each edge e E(G); but then this is equivalent to saying (G e) =
(G) 1. If (G) = 1, then G is either trivial or totally disconnected. Hence G is 1-critical if
and only if G is K
1
. Also (G) = 2 implies that G is bipartite and has at least one edge. Hence
G is 2-critical if and only if G is K
2
.
It is clear that any k-chromatic graph contains a k-critical subgraph. This can be seen by
removing vertices and edges in succession, whenever possible, without decreasing the chromatic
number.
Theorem 7.1:
If G is k-critical, then (G) k 1.
Proof. Suppose (G) k 2. Let v be a vertex of minimum degree in the graph G. Since G is
k-critical, (Gv) = (G) 1 = k 1 (refer Exercise ??). Hence in any proper (k 1)-coloring
of Gv, at most (k 2) colors alone would have been used to color the neighbors of v in G. Thus
there is at least one color, say c, that is left out of these (k 1) colors. If v is given that color
April 2007 24 CSE/NIT
Graph theory K. V. Iyer
c, a proper (k 1)-coloring of G is obtained. This is impossible since G is k-chromatic. Hence
(G) (k 1).
7.2 Bounds for (G)
A corollary to Theorem 7.1 is: For any graph (G) 1 + (G).
Proof. Let G be a k-chromatic graph and let H be a k-critical subgraph of G. Then (H) =
(G) = k. By Theorem 7.1, (H) k 1 and hence k 1 +(H) 1 + (H) 1 + (G).
The above result is implied by the greedy coloring algorithm given below.
Algorithm GREEDY-COLORING
Given V (G), let v
1
, v
2
, . . . , v
n
be a vertex ordering, where |V (G)| = n. Color the vertices in this
order, assigning to v
i
the smallest-indexed label (color) not already used on its lower-indexed
neighbors.
In a vertex ordering, each vertex v has at most (G) neighbors prior to v in the ordering. So
the algorithm GREEDY-COLORING cannot be forced to use more than (G)+1 colors. (reason:
v has at most (G) vertices adjacent to it; for coloring these adjacent vertices we need (G)
colors and a dierent color for coloring v itself). This constructively proves that (G) (G)+1.
If G is an odd cycle, then (G) = 3 = 2 +1 = 1 +(G); if G is a complete graph K
k
, (G) =
k = 1 + (k 1) = 1 + (G). That these are the only two extremal families of graphs for which
(G) = 1 + (G) is asserted by the following theorem.
Theorem 7.2 (Brooks Theorem):
If G is a connected graph other than a complete graph or an odd cycle, then (G) (G).
Proof. Assume that G is a connected graph that is not a complete graph or an odd cycle. Let
k = (G). If k = 1, G is a clique and if k = 2, then G is an odd cycle or is bipartite; so we may
assume, that k 3. We distinguish between the following two cases.
1. G is not k-regular: In this case we choose vertex v
n
so that d(v
n
) < k. Since G is connected
we can grow a spanning tree of G from v
n
assigning indices in the decreasing order as we
reach vertices. Each vertex other than v
n
in the resulting ordering v
1
, . . . , v
n
has a higher
April 2007 25 CSE/NIT
Graph theory K. V. Iyer
indexed neighbor along the path to v
n
in the tree. Therefore each vertex has at most k 1
lower indexed neighbors and the algorithm GREEDY-COLORING used at most k colors.
2. G is k-regular: If G has a cut vertex x, let G

be a component of G x together with

its edges incident on x. Now d
G
(x) < k and we can obtain a proper k-coloring of G

as above. By appropriately we can make the colorings agree on x to complete a proper

k-coloring of G. If G does not have a cut vertex, since it is connected, we can assume that
it is 2-connected. Suppose G has an induced 3-vertex path with vertices say v
1
v
n
v
2
in that
order such that G{v
1
, v
2
} is connected. We can then label the vertices of a spanning tree
of G{v
1
, v
2
} using indexes 3, . . . , n such that the labels increase along paths to the root
v
n
. Reasoning as before, we can assert that each vertex before v
n
has at most k 1 lower
indexed neighbors. Algorithm GREEDY-COLORING also uses at most k 1 colors. On
the neighbors of v
n
since v
1
and v
2
receive the same color. It is non sucient to show that
every 2-connected k regular graph with k < 3 has three such vertices. Choose a vertex x
in G. If k(Gx) 2, let v
1
be x and let v
2
be a vertex at distance two from x v
2
exists
because G is regular and not a clique. If k(Gx) = 1, then x has a neighbor in every leaf
block of G x (note: G has no cut vertex). The neighbors v
1
, v
2
of x in two such blocks
are nonadjacent. Also, G {x, v
1
, v
2
} is connected since blocks have no cut-vertices. Now
k 3 implies that G{v
1
, v
2
} is also connected and we let v
n
= x.
April 2007 26 CSE/NIT
Graph theory K. V. Iyer
Exercises
1. Prove that two graphs G and H are isomorphic if and only if

G and

H are isomorphic.
2. The line-graph L(G) of a given graph G = (V, E) is the simple graph whose vertices are
the edges of G with ef E
_
L(G)
_
if and only if two edges e and f in G have a common
endpoint. Verify that the Petersen graph is the complement of the line-graph of K
5
.
3. Prove that if G is a self-complementary graph with n vertices, then n is either 4t or 4t +1,
for some integer t. Construct examples of self-complementary graphs.
4. Let G be the graph whose vertex set is the set of binary strings of length n (n 1) . A
vertex x in G is adjacent to vertex y of G if and only if x and y dier exactly in one position
in their binary representation. Prove that G is a bipartite graph.
5. Let G be a simple graph. Show that if G is not connected, then its complement

G is
connected.
6. Give a construction by which you produce an innite number of regular graphs starting
from a given regular graph.
7. Consider any k-regular graph G for odd k. Prove that the number of edges in G is a multiple
of k.
8. Prove that every 5-regular graph contains a cycle of length at least six.
9. Explore the degree sequence of a graph.
10. Let A be the adjacency matrix of a connected graph G with n vertices; it is it necessary to
compute up to A
n1
to conclude that G is connected. True/false? justify.
11. Prove or disprove: Let G be a simple connected graph with |V | 3. Then G has a cut edge
if and only if it has a cut vertex.
12. With reference to enumerating trees explore the bijection between Pr ufer codes and labeled
trees.
13. For any two spanning trees T
1
, T
2
prove that T
2
can be obtained from T
1
by the operations
of edge deletions and additions, passing through a sequence of trees.
April 2007 27 CSE/NIT
Graph theory K. V. Iyer
14. Let G be a graph with exactly one spanning tree. Prove that G is a tree.
15. If = k, then show that a graph G has a spanning tree with at least k leaves.
16. Prove the following.
(i) W(K
n
) =
_
n
2
_
.
(ii) W(K
m,n
) = (m+n)
2
mn mn.
(iii) W(C
2n
) = (2n)
3
/8.
(iv) W(C
2n+2
) = (2n + 2)(2n + 1)(2n)/8.
(v) Wiener index of the Petersen Graph is 75.
17. Find the Wiener index of the graph P
n
P
n
, where n > 1.
18. Prove that (G) = 2 if and only if G is a bipartite graph with at least one edge.
19. What is an L(2, 1) labeling of a graph? Given an L(2, 1) labeling l of a graph G, let k =
max. label in l. The min. k over all possible L(2, 1) labelings is (G). Prove that (K
n
) is
odd.
20. Prove that every critical graph is connected.
21. Show that if G is k-critical, then for any v V (G) and e E(G),
(Gv) = (Ge) = k 1.
April 2007 28 CSE/NIT
Graph theory K. V. Iyer
References
[1] R.Balakrishnan and K.Ranganathan, A textbook of graph theory, Springer, 2000.
[2] E. Bertram and P. Horak, Some applications of graph theory to other parts of mathematics,
The Mathematical Intelligencer, 21(3) 1999, 6-11.
[3] G.Chartrand and P.Zhang, Introduction to graph theory, McGraw-Hill, 2005.
[4] F. Harary, Graph Theory, Addison-Wesley, 1969.
[5] J. Matousek and J. Nesetril, Invitation to Discrete Mathematics, Clarendon Press, Oxford,
1998.
[6] D.B.West, Introduction to graph theory, Prentice-Hall, 1996.
April 2007 29 CSE/NIT