Graph Theory

MANOJ KUMAR SINGH∗

Department of Mathematics
St. Xavier’s College, Ranchi-834001, Jharkhand

Note: The purpose of this handout is to help students in their studies in Graph Theory.
Students are advised to consult books for better treatment of the subject.

The Konigsberg Bridge Problem. The city of Konigsberg was located on the Pregel river
in Prussia. The city occupied two islands plus areas on both banks. These regions were linked
by seven bridges. The citizens wondered whether they could leave home, cross every bridge
exactly once, and return home. The problem reduces to traversing the figure below, with heavy
dots representing land masses and curves representing bridges.

Figure 1: KONIGSBERG BRIDGE PROBLEM

Definition. A graph G is a pair (V, E), where V is a non-empty finite set, and E is a set of un-
ordered pairs of elements of V. The elements of V are called the vertices of G, and the elements
of E are the edges of G. We always assume that V ∩ E = φ .

The set of vertices of a graph G may be written V (G); the number |V (G)| of vertices is
the order of G, denoted by n(G) or just n. The set of edges may be written E(G); the number
|E(G)| of edges is the size of G, denoted by m(G) or just m. The edge joining the vertices u
and v is denoted by {u, v} or just uv.

Definition. A vertex v is said to be incident with an edge e if v is one of the vertices of the edge
e.

Definition. Vertices u and v of a graph G are adjacent if uv ∈ E(G). Two distinct edges e and
f are said to be adjacent if there is a vertex incident with both of them. Vertices u and v are
∗ manojksingh88@gmail.com

1
said to be independent if there is no edge between them.

Definition. A graph is said to be finite if its vertex set and edge set are finite otherwise infinite.

Definition. The null graph is the graph whose edge set is empty.

Definition. A loop is an edge whose end vertices are same. Multiple edges (parallel edges)
are edges having the same pair of endpoints. A simple graph is a graph having no loops or
multiple edges.

Figure 2: Loop

Q. Draw all simple graphs G such that |V (G)| ≤ 3.

n(n−1)
Q. Show that the maximum number of edges in a simple graph with n vertices is 2 .

Definition. The degree of a vertex v of a graph G is the number of vertices incident with v. It
is denoted by degG v or just deg(v). The minimal degree of the vertices of a graph G is denoted
by δ (G) and the maximal degree by ∆(G).

Definition. A vertex having no incident edge is called an isolated vertex. It can also be defined
as a vertex of degree 0.

Q. (T/F) Max. degree of any vertex in a simple graph with n vertices in (n − 1). (Justify)

Theorem 1. Sum of the degrees of all the vertices in G is twice the number of edges in G.
Proof: Since each edge has two vertices so each edge contribute 2 to the sum of degree of
each vertices. Hence,

∑ degGv = 2|E(G)|. (1)

v∈G

Definition. A vertex is called even or odd according as its degree is even or odd.

Theorem 2. The number of vertices of odd degree in a graph is always even.

2
 Proof: Let A and B be sets consisting of vertices of even degree and odd degree. By (1),
we have

∑ degGv + ∑ degGv = 2|E(G)|

v∈A v∈B
=⇒ ∑ degGv + ∑ degGv is even.
v∈A v∈B
=⇒ ∑ degGv is even.
v∈B

Hence number of odd vertices is even.

Definition. A graph G is called regular if each vertex in G has the same degree.

Definition. A simple graph in which there exists an edge between every pair of vertices is called
a complete graph. The complete graph on n vertices will be denoted by Kn .

Figure 3: K4 and K5

Note: K4 and K5 are also regular graph.

Definition. A graph G is said to be bi-partite if there is a partition of V (G) into two sets V1 and
V2 , called partite sets, such that every edge has one vertex in V1 and another in V2 . In simple
words each edge in G has one end in V1 and another in V2 . A bi-partite graph with partition
(V1 ,V2 ) is called complete bi-partite graph if each vertex in V1 is joint to every vertex in V2
by just one edge. The complete bipartite graph with r vertices in one partite set and s in the
other is denoted by Kr,s .

Q1. Show that the maximum number of edges in a complete bipartite graph of n vertices is
n2
.
4
Q2. Prove that a graph is bipartite if and only if all its cycles are of even length.

Definition. Complement of a Graph: Let G be a loop-free graph on n vertices. The comple-

ment of G, denoted G, is the subgraph of Kn consisting of the n vertices in G and all edges that
are not in G. (If G = Kn then G is a graph consisting of n vertices and no edges i.e. null graph.)

3
Definition. Isomorphic Graphs: Let G1 and G2 be graphs. An isomorphism from G1 to G2
is a bijection f : V (G1 ) → V (G2 ) such that uv ∈ E(G1 ) iff f (uv) ∈ E(G2 ). In other words, we
say that two graphs are isomorphic if there is a correspondence between their vertex sets that
preserve adjacency.

Figure 4: Isomorphic Graphs

Figure 5: Non Isomorphic Graphs

Definition. A Spanning subgraph of a graph G is a subgraph H with V (H) = V (G).

Note: If G is a graph then deleting all loops and all the parallel edges except one between
a pair of vertices then we obtain a simple spanning subgraph of G called underlying simple
graph of G.

Figure 6: Graph and its spanning graph

Union and Intersection of Graphs: Let G = (V1 , E1 ) and G0 = (V2 , E2 ) be two graphs
then their union and intersection are defined as G ∪ G0 = (V1 ∪V2 , E1 ∪ E2 ) and G ∩ G0 =
(V1 ∩V2 , E1 ∩ E2 ).

Definition. Edge-Disjoint Subgraphs: Two (or more) subgraphs G1 and G2 of a graph G are
said to be edge disjoint if G1 and G2 do not have any edges in common.

Definition. Decomposition: A graph G is said to have been decomposed into two subgraphs
G1 and G2 if G1 ∪ G2 = G and G1 ∩ G2 = a null graph.

4
Definition. A subgraph of a graph G is a graph H with V (H) ⊆ V (G) and E(H) ⊆ E(G). We
write H ⊆ G. If U is any proper subset of V (G), G −U is the subgraph obtained by deleting all
vertices of U and all edges with at least one vertex in U.

Definition. A walk is defined as a finite alternating sequence of vertices and edges, beginning
and ending with vertices, such that each edge is incident with the vertices preceding and fol-
lowing it and does not appear more than once. A walk is closed if its first and last vertices are
same, and open if they are different.The length of walk is defined to be number of edges in
walk.

Figure 7: An Open Walk

Definition. A walk is said to be a trail if no edge is repeated in the walk. An open walk in
which no vertex appears more than once is called a path.

Definition. A closed walk in which no vertex (except the initial and the final vertex) appears
more than once is called a Cycle (circuit). Length of a path and cycle is defined as the number
of edges it contains.

Figure 8: Three different cycles

Theorem 3. A graph is bipartite if and only if it contains no odd cycle.

Proof: Suppose that G is bipartite with bipartition (X,Y ) and let C = v0 v1 v2 .....vk v0 be a
cycle of G. Without loss of generality we may assume that v0 ∈ X. Then, since v0 v1 ∈ E and G
is bipartite, vk ∈ Y . Similarly v2 ∈ X. In general, v2i ∈ X and v2i+1 ∈ Y . Since v0 ∈ X, vk ∈ Y .
Thus k = 2i + 1, for some i, and it follows that C is even.

5
 It is sufficient to prove the converse for connected graphs. Let G be a connected
graph that contains no odd cycles. We choose an arbitrary vertex u and define a partition (X,Y )
of V by setting

X = {x ∈ V (G)| d(u, x)is even}

Y = {y ∈ V (G)| d(u, y)is odd}

We shall show that (X,Y ) is a bipartition of V (G). Also we need to show that G is bipartite
graph we have to show that no two vertices of X (similarly of Y ) are not adjacent.
Suppose that v and w are two vertices of X. Let P be the shortest uv path and
Q be the shortest uw path. Denote by u1 the last vertex common to P and Q. Since P and Q are
shortest path, the uu1 sections of P and Q are shortest uu1 paths and, therefore, have the same
length. Now, since the lengths of both P and Q are even, the lengths of the u1 v section (say P1
of P) and u1 w section (say Q1 of Q) are of same parity of length. Hence,the vw path P1−1 Q1
is of even length. If v were joined to w, P1−1 Q1 wv would be a cycle of odd length, contrary to
the hypothesis. Therefore no two vertices in X are adjacent; similarly, no two vertices in Y are
adjacent.

Definition. A graph G is said to be connected if there is at least one path between every pair of
vertices in G. In other words a graph is said to be connected if there exists a uv path whenever
u, v ∈ V (G). A graph is said to be disconnected if it is not connected.

Definition. Component of a graph: We define a relation R in V (G) such that uRv iff there
exists a uv path in G. Clearly, the relation R is an equivalence relation, and equivalence classes
are called components of a graph. Each component is connected, and every connected subgraph
of G is contained in a component. The number of components is denoted by k(G). Thus
k(G) = 1 iff G is connected.
Component of a graph can also be defined as maximal connected subgraph of G.

Theorem 4. A graph G is disconnected iff its vertex set V can be partitioned into two non-
empty, disjoint subsets V1 and V2 such that there exists no edge in G whose one end vertex is in
subset V1 and the other in subset V2 .

Proof: Suppose that such a partitioning exists. Consider two arbitrary vertices a and b of
G, such that a ∈ V1 and b ∈ V2 . No path can exist between vertices a and b; otherwise there
would be at least one edge whose one end vertex would be in V1 and the other in V2 : Hence, if
a partition exists, G is not connected.

Conversely, let G be a disconnected graph. Consider a vertex a in G. Let V1 be the

set of all vertices that are connected by paths to a. Since G is disconnected, V1 does not include
all vertices of G. The remaining vertices will form a (non-empty) set V2 . No vertex in V1 is
connected to any vertex in V2 by path. Hence the partition exists.

6
Theorem 5. If a graph (connected or disconnected) has exactly two vertices of odd degree,
there must be a path joining these two vertices.
Proof: Let G be a graph with all even vertices except vertices v1 and v2 , which are odd. By
theorem 2, no graph can have an odd number of odd vertices. Therefore, in graph G, v1 and v2
must belong to the same component, and hence there must be a path between them.

Theorem 6. If W is a walk connecting u and v in a graph G then W contains a path connecting

u and v.
Proof: Let P(u, v) be a subwalk of W connecting u and v such that P(u, v) has minimum
length.
claim: P(u, v) is a path.
On contrary, assume that there is a vertex 0 a0 in the subwalk P(u, v) such that it appears more
than once in the subwalk P(u, v).

So, P(u, v) = (u =)u0 e1 u1 e2 ........u j−1 e j u j (= a)e j+1 u j+1 .......ek−1 uk−1 ek uk (= a)ek+1 uk+1 ........un (=
v)

Figure 9: P(u, v)

But then the sequence (u =)u0 e1 u1 e2 ........u j−1 e j u j ek+1 uk+1 ........un (= v) obtained by delet-
ing the subwalk e j+1 u j+1 .......ek−1 uk−1 ek is a walk connecting u and v of length smaller than
P(u, v) but this a contradiction as we have assumed that P(u, v) has minimum length. Hence
P(u, v) is a path.

Notation:
• δ (G) = min. degree of the graph = min. {d(vi ); vi ∈ V (G)}

• ∆(G) = max. degree of the graph = max. {d(vi ); vi ∈ V (G)}

• ω(G) = no. of components of a graph G.

Theorem 7. If G is a simple graph such that δ (G) ≥ 2 then G contains a cycle of length atleast
δ + 1.
Proof: Let P be a path of maximum length in G. Let v1 and vn be its initial and terminal
vertices.
Let P = v1 e1 v2 e2 ....vn−1 en−1 vn . Let d(v1 ) = t + 1 as δ (G) ≥ 2 =⇒ t ≥ 1 and so there
are t distinct vertices say u1 , u2 , ....., ut adjacent with v1 besides v2 .

claim: {u1 , u2 , ....., ut } ⊆ {v3 , v4 , ....., vn }.

7
 Figure 10: Path P

If not, then there exist uk such that uk ∈ {u1 , u2 , ....., ut }\{v3 , v4 , ....., vn }, then
the path uk v1 e1 v2 .....vn has length greater than the length of the path P, which is a contradiction.

Hence we have, {u1 , u2 , ....., ut } ⊆ {v3 , v4 , ....., vn }.

Let j be the greatest integer such that v j = ui for some i, clearly the minimum value of
j is t + 2. Also, v1 e1 v2 ......v j e j v1 is a cycle of length atleast t + 2, which is d(v1 ) + 1 ≥ δ + 1.
So, it has a cycle of length at least δ + 1.

Theorem 8. Every (p, q) graph with q ≥ p contains a cycle.

Proof: By induction on p (number of vertices) Clearly the result holds for p = 1, 2, 3 and
q ≥ p.
Now, we assume that every graph on (p − 1) vertices with q ≥ p − 1 contains a cycle.

Let H be a graph on p vertices with q(H) ≥ p. If δ (H) ≥ 2 then H contains a

cycle by previous theorem. So, assume δ (H) ≤ 1. Let v be the vertex such that d(v) ≤ 1. Now,
consider the graph H − v, we have
no. of vertices in H − v = p − 1
no. of edges in H − v ≥ q − 1

but q ≥ p, so q − 1 ≥ p − 1. Hence H − v contains a cycle and hence H contains a cycle.

Theorem 9. A connected (p, q) graph contains a cycle iff q ≥ p.

Proof: By above theorem, a connected graph contains a cycle if q ≥ p. Conversely, assume

that a connected (p, q) graph contains a cycle . We have to prove that q ≥ p.

Proof by induction

Clearly the result holds for p ≤ 3. Let us assume that every connected graph con-
taining a cycle on (p − 1) vertices has atleast (p − 1) edges.

Let G be a connected graph on p vertices which contains a cycle C.

If δ (G) ≥ 2, then
1 1
q(G) = ∑ d(v) ≥ ∑ 2 = p(G) =⇒ q(G) ≥ p(G).
2 v∈V 2 v∈V

8
 Now, let δ (G) = 1 and let v be a vertex of degree 1. Now, G − v is a graph on p − 1 vertices.
Clearly, v can’t be a vertex in a cycle C as d(v) = 1. So, G − v contains cycle C and hence by
induction hypothesis, we have q(G − v) ≥ p(G − v). Also, q(G) = q(G − v) + 1. Hence,
q(G − v) + 1 ≥ p(G − v) + 1
=⇒ q(G) ≥ p(G).
Theorem 10. If q ≥ (p − 1) then every (p, q) graph is either connected or contains a cycle.
Proof: Proof by contradiction

Let G be a (p, q) graph with q ≥ (p − 1) which is neither connected nor contains a

cycle. Let G1 , G2 , G3 , ........, Gt (t ≥ 2) be the t components of G. let Gi has pi vertices and qi
edges (1 ≤ i ≤ t).
Since each component is without a cycle, it follows that qi ≤ pi − 1 for each i. Hence
q = q1 + q2 + ........ + qt
≤ (p1 − 1) + (p2 − 1) + ....... + (pt − 1)
= (p1 + p2 + .......pt ) − t
≤ p−t
which is a contradiction. Hence, if q ≥ (p − 1) then every (p, q) graph is either connected or
contains a cycle.
Theorem 11. For any graph G, q(G) ≥ p(G) − ω(G).
Proof: For p = 1, p(G) − ω(G) = 0. Hence theorem holds for p = 1.

Let us assume that the result holds good for a graph having
vertices less than p. Let G be a graph on p vertices. If δ (G) ≥ 2, then
1 1
q(G) = ∑ d(v) ≥ ∑ 2 = p(G)
2 v∈V 2 v∈V
=⇒ q(G) ≥ p(G)
=⇒ q(G) ≥ p(G) − ω(G)
If δ (G) < 2, then we have two possibilities.
1. G has a vertex of degree 0.
2. G has a vertex of degree 1.
Let G has a vertex v of degree 0, then we consider the graph H = G − v, then
p(H) = p(G) − 1, q(H) = q(G) and ω(H) = ω(G) − 1.
So, by induction hypothesis,
q(H) ≥ p(H) − ω(H)
=⇒ q(G) ≥ p(G) − 1 − (ω(G) − 1)
≥ p(G) − ω(G).

9
 Next, let G has a vertex v of degree 1. Again, we consider the graph H = G − v, hence

p(H) = p(G) − 1, q(H) = q(G) − 1 and ω(H) = ω(G).

Now, by induction hypothesis

q(H) ≥ p(H) − ω(H)

=⇒ q(G) − 1 ≥ p(G) − 1 − ω(G)

thus, in any case q(G) ≥ p(G) − ω(G).

Corrolary: If G is a connected graph then q(G) ≥ p(G) − 1.

(n−k)(n−k+1)
Theorem 12. A simple graph with n vertices and k components can have at most 2
edges.

Proof: Let G be a simple graph with n vertices and k components. Let n1 , n2 , n3 , ......, nk be
the number of vertices in each of the k components of G. Then we have

n1 + n2 + ..... + nk = n ; ni ≥ 1 ∀ i

Since the maximum number of edges in a simple graph with n vertices is n(n−1)
2 , therefore
th 1
maximum number of edges in the i component of G is 2 ni (ni − 1), thus the maximum number
of edges in G is
" #
k
ni (ni − 1) 1 k 2 k
∑ 2 = 2 ∑ ni − ∑ ni (2)
i=1 i=1 i=1

Now, using the inequality ∑ki=1 n2i ≤ n2 − (k − 1)(2n − k), above equation can be written as
k
ni (ni − 1) 1 2 
∑ ≤ n − (k − 1)(2n − k) − n
i=1 2 2
1
= (n − k) (n − k + 1).
2

10
Definition. TREE: A connected graph without any cycle is called tree.

Figure 11: Tree

Theorem 13. A graph G is a tree iff there is one and only one path between any two vertices
of G. (This can be stated as ”A graph G is a tree iff every two vertices of G are connected by a
unique path”)

Proof: Let G be a tree. Let there are two distinct uv paths P1 and P2 in G. Since P1 6= p2 ,
there is an edge e = xy of P1 which is not an edge of P2 . Clearly the graph P1 ∪ P2 − e is con-
nected and so it contains an xy path P but then P + e is a cycle in G, a contradiction to the fact
that G is a tree.

Conversely, let us assume that every two vertices are connected by a unique path.
Clearly, G is connected. Now If G contains a cycle (u =)u0 u1 u2 .......uk (= v)uk+1 uk+2 ......un (=
u0 = u), then the paths u0 u1 u2 .......uk and un un−1 .........uk are two distinct uv paths, contrary to
our assumption. So, G is a connected graph without any cycle and hence a tree.

Theorem 14. A tree with n vertices has n − 1 edges.

Proof: Proof by induction on number of vertices.

Clearly the theorem is true for trees with one and two vertices. Assume that the
theorem is true for all trees with fewer than n vertices.

Let us consider a tree G with n vertices. Let ek be an edge in G with end

vertices vi and v j . Then by previous theorem the edge ek is the only path between vi and v j .
Hence, deletion of ek from G will disconnect the graph G. Thus G−ek is not connected. Further
G − ek will contain exactly two components, for otherwise the graph G will not be connected.
Let the two components of G − ek be G1 and G2 . Each of these components is a tree because
there were no cycles in G. Let n1 and n2 be the number of vertices in G1 and G2 .

Clearly n1 ≤ n and n2 ≤ n, so by induction hypothesis

number of edges in G1 = n1 − 1
number of edges in G2 = n2 − 1

Thus number of edges in G − ek = n1 + n2 − 2 and hence number of edges in G = n1 + n2 −

2 + 1 = n1 + n2 − 1 = n − 1.

11
Theorem 15. Every connected graph with n vertices and n − 1 edges is a tree.

Proof: Let G be a connected graph with n vertices and n − 1 edges. We need to prove that
G does not contain any cycle.

Suppose that G contains at least one cycle. Since removing an edge from a cy-
cle does not disconnect the graph, we may remove edges from cycle but no vertices until the
resulting graph G∗ is cycle free.

Now, G∗ is a connected graph with n vertices containing no cycle. Thus G∗ is

a tree with n vertices. Hence G∗ has n − 1 edges but G∗ was obtained by deleting some edges
from G. Hence G has more than n − 1 edges, which is a contradiction.

Hence G has no cycle and hence a tree.

Theorem 16. A graph G with n vertices, n − 1 edges and no cyles is a tree.

Proof: Let G be a graph with n vertices, n − 1 edges and has no cycles. To show that G is a
tree, it is sufficient to prove that G is connected.

If possible, suppose that G is disconnected. Then G consists of two or more

components. Without loss of generality, assume that G has two components G1 and G2 . Con-
sider two vertices v1 in G1 and v2 in G2 . Since v1 and v2 are in different components of G, there
is no path between v1 and v2 in G. Now we add an edge e from v1 and v2 . Clearly, by adding
an edge e between v1 and v2 , we do not obtain any cycle as there was no path between v1 and v2 .

Thus G ∪ e does not contain any cycle and is a connected graph and therefore
we obtain a tree having n vertices and n edges, which is not possible. Hence the theorem.

Definition. Minimally Connected Graph: A connected graph G is said to be minimally con-

nected if removal of any edge from G disconnects the graph G.

Theorem 17. A graph G is a tree iff it is minimally connected.

Proof: Suppose that G is a tree, so it connected. If G is not minimally connected then there
exist an edge e in G such that G − e is connected. Therefore e is in some cycle. So, G has a
cycle, hence G is not a tree which is a contradiction. Hence G has to be minimally connected.

Conversely, assume that G is a minimally connected graph.

Claim: G cannot have a cycle.

If G has a cycle, then by removing an edge of the cycle does not disconnect G, so G
is not a minimally connected which is a contradiction. Hence G is a tree.

12
Definition. Let G be a connected graph and vi and v j be any two vertices in G. The distance
between the vertices vi and v j denoted by d(vi , v j ) is defined as the length of smallest path
between vi and v j .

Q. Show that the distance between vertices of a connected graph is a metric.

Definition. Eccentricity of a Vertex: The eccentricity E(v) of a vertex v in a graph G is the

distance between v and the vertex vi farthest from v in G. Symbolically

E(v) = max.{d(v, vi ) : vi ∈ V (G)}

Definition. Center of a graph: Center of a graph is a vertex whose eccentricity in G is minimal.

Theorem 18. Every tree has center consisting of either one vertex or two adjacent vertex.

Proof: Clearly the result holds for a graph having one or two vertices. Let T be a tree
having more than two vertices. Clearly, maximum of distance from a given vertex u of T to any
vertex v of T will occur only when v is an end vertex of T.

Let T’ be a tree obtained by removing all end vertices of T, then eccentricity

of each vertex of T will be exactly one less than its eccentricity in T. Hence the vertices having
minimum eccentricity in T are same vertices in T’ having minimum eccentricity.

Thus T and T’ have same center. Let T” be the tree obtained by removing
all end vertices of T’ then with the same argument above, we note that T’ and T” will have
same center which is also center of T. Continuing this process of removing end vertices, we
arrive at a graph having just one vertex or two vertices, which will have the same center as that
of T, thus center of T consists of a single vertex or two adjacent vertices.

Definition. Radius of a tree: The eccentricity of center in a tree is called the radius of the tree.

Definition. Diameter of a tree: The diameter of a tree T is defined as the length of the longest
path in T.
Definition. Spanning Tree: A subgraph T of a connected graph G is said to be spanning tree
of G if the subgraph T is a tree and contains all the vertices of G.

Figure 12: Graph and its Spanning tree

13
Theorem 19. Every connected graph has atleast one spanning tree.

Proof: Let G be a connected graph. If G has no cycles then it is its own spanning tree. If
G has a cycle then delete an edge from each cycle then the graph G remains connected and we
get a connected graph Ḡ having no cycles. hence Ḡ is a tree and hence spanning tree of G.

Definition. Cut Edge: An edge e is said to be a cut edge of G if ω(G − e) > ω(G).

Theorem 20. An edge e of G is a cut edge of G iff e is contained in no cycle of G.

Proof: Let e be a cut edge of G, then ω(G − e) > ω(G). So there exists two vertices u and
v of G which are connected in G but not in G − e, so there exists some uv path P in G which
necessarily transverses e. Suppose x and y are end vertices of e and x precedes y on P. In G − e,
u is connected to x by a section of P and y is connected to v by a section of P.

If e were in a cycle C, x and y would be connected in G − e by the path

(C − e). Thus u and v would be connected in (G − e) , contradiction.

Conversely, Let e = xy is contained in no cycle of G. If possible, let e is not a

cut edge of G, then
ω(G − e) = ω(G).
Since there is an xy = e path in G, xy are in the same components of G − e and hence there is
an xy path P in G − e but then e is contained in cycle P + e, a contradiction.

Theorem 21. A connected graph is a tree iff its every edge is a cut edge.

Proof: Let G be a tree and e is an edge of G as G has no cycle, so e is contained in no

cycle, then e is an cut edge. Conversely, let G be a connected graph whose every edge is a cut
edge. If possible let G is not a tree, then G contains a cycle C and no edge of C is a cut edge, a
contradiction.

Definition. Cut Vertex: A vertex v of a graph G is said to be a cut vertex if ω(G − v) > ω(G).

Definition. Binary Tree: A binary tree is defined as a tree in which there is exactly one vertex
of degree two and each of the remaining vertices is of degree one or three.
Note: The number of vertices in a binary tree is always odd as there is exactly one vertex
of even degree and the remaining (n − 1) vertices are of odd degree. Hence n is odd.

Q 1. What is the maximum number of vertices in a graph with 35 edges and all vertices are
of degree at least 3.
Ans: Let n be the number of vertices. Since the graph has 35 edges and each edge contribute
2 to the sum of degrees of all vertices, therefore sum of degrees of all vertices is 2 × 35 = 70.
Also, each vertex is of degree at least 3, therefore 3n ≤ 70 ⇒ n ≤ 23.3. Hence maximum
number of vertices in a graph with 35 edges such that each vertex is of degree at least 3 is 23.

14
Definition. Incidence Matrix: Let G be a graph with n vertices v1 , v2, ......, vn and m edges
e1 , e2 , ......, em and no self loops. We define an n × m matrix A = ai j whose n rows corre-
sponding to n vertices and m columns corresponding to m edges as follows

if vi is one of the end points of the jth edge.


1
ai j =
0 otherwise
 
then the matrix A = ai j is called incidence matrix of G.

Q. Write the incidence matrix of the following graph?

Figure 13: Graph G

Ans:
 
1 0 0 0 0
0 1 1 0 0
 
0 0 0 1 0
 
0 0 1 1 1
 
1 1 0 0 1
0 0 0 0 0
Properties of Incidence Matrix

1. Each column of incidence matrix A of a graph G without self loops has exactly two 10 s
because each edge is incident on exactly two vertices.
2. Given an incidence matrix, we can draw the corresponding graph.
3. Sum of each row gives the degree of the corresponding vertex.
4. If a graph has multiple edges then the corresponding columns in the incidence matrix are
identical.
5. A row with all zero’s represents an isolated vertex.
6. In changing any two rows or columns in an incidence matrix simply corresponds to rela-
beling the vertices and edges of the same graph. Thus two graphs G1 and G2 are isomor-
phic if the incidence matrix of one graph can be obtained from the incidence matrix of
the other by interchanging some of the rows and the columns.

15
 7. Rows of A are linearly dependent if graph does not contain any parallel edges.

Definition. Adjacency Matrix: Adjacency Matrix of a graph with n vertices and no multiple
edges (self loops are allowed) is an n × n matrix X = xi j where

if there is an edge between ith and jth vertices,


1
xi j =
0 if there is no edge between them.
 
0 0 0 0 1 0
0 0 0 1 1 0
 
0 0 0 1 0 0
M=
0

 1 1 0 1 0

1 1 0 1 0 0
0 0 0 0 0 0
Properties of Adjacency Matrix

1. Adjacency matrix X(G) of a graph G is symmetric.

2. If graph has no self loops then the diagonal entries of X(G) are zero and vice- versa.

3. If the graph has no self loops then the sum of the ith row is the degree of vi .

4. Two graphs G1 and G2 are isomorphic iff the adjacency matrix of one can be obtained
from the adjacency matrix of the other by interchanging some of the rows and the corre-
sponding columns.

5. Given any square, symmetric matrix X of order n, we can draw a graph G with n vertices
and no multiple edges.

  Cycle Matrix: Let G be a graph with q cycles and n edges, then a cycle matrix
Definition.
B = bi j of G is a q × n matrix with bi j ∈ {0, 1}, 1 ≤ i ≤ q, 1 ≤ j ≤ n such that

if the ith cycle includes jth edge,


1
bi j =
0 otherwise.
 
1 1 0 0 0
M=
0 1 0 1 0

16
 Figure 14: Graph G

Properties of Cycle Matrix

1. A column of all zeroes corresponds to a non cycle edge.

2. Each row of B(G) is a cycle vector.

3. The number of 10 s in a row is equal to the number of edges in the corresponding cycle.
 
Definition. Path Matrix: A path matrix P(u, v) = pi j is defined for a given pair of vertices
in a graph say (u, v) is defined as

if jth edge lies in the ith path,


1
pi j =
0 otherwise.

Properties of Path Matrix

1. A column of all zeroes corresponds to an edge that does not lie in any path between u
and v.

2. A column of all one’s corresponds to an edge that lies in every path between u and v.

3. There cannot be row with all zeroes.

Definition. Euler Line: A closed walk in a graph contains all the edges of the graph is called
an Euler line . A trail that traverses every edge of G is called an Euler trail of G. Hence,
Euler line is closed Euler trail. A graph which contains an Euler line is called an Euler graph
(Eulerian Graph).

Theorem 22. A connected graph G is an Euler graph if and only if all vertices of G are of even
degree.

Proof: Above theorem can be stated as ”A non empty connected graph is Eulerian if and only
if it has no vertices of odd degree.”
Suppose that G is an Euler graph. It therefore contains an Euler line (which is a closed walk).
In tracing this walk we observe that every time the walk meets a vertex v it goes through two
”new” edges incident on v-with one we ”entered” v and with the other ”exited.” This is true not
only of all intermediate vertices of the walk but also of the terminal vertex, because we ”exited”

17
and ”entered” the same vertex at the beginning and end of the walk, respectively. Thus if G is
an Euler graph, the degree of every vertex is even.
To prove the converse, assume that all vertices of G are of even degree. Now we
construct a walk starting at an arbitrary vertex v and going through the edges of G such that no
edge is traced more than once. We continue tracing as far as possible. Since every vertex is of
even degree, we can exit from every vertex we enter; the tracing cannot stop at any vertex but
v. And since v is also of even degree, we shall eventually reach v when the tracing comes to an
end. If this closed walk H we just traced includes all the edges of G, G is an Euler graph. If not,
we remove from G all the edges in H and obtain a subgraph H’ of G formed by the remaining
edges. Since both G and H have all their vertices of even degree, the degrees of the vertices of
H’ are also even. Moreover, H’ must touch H at least at one vertex a, because G is connected.
Starting from a, we can again construct a new walk in graph H’. Since all the vertices of H’ are
of even degree, this walk in H’ must terminate at vertex a; but this walk in H’ can be combined
with H to form a new walk, which starts and ends at vertex v and has more edges than H. This
process can be repeated until we obtain a closed walk that traverses all the edges of G. Thus G
is an Euler graph.
Corollary 1. A connected graph has as Euler trail if and only if it has at most two vertices of
odd degree.
Proof: If G has an Euler trail then, arguments as is given in previous theorem, each vertex
other than the origin and terminus of this trail has even degree.
Conversely, suppose that G is a nontrivial connected graph with at most two vertices of
odd degree. If G has no such vertices of odd degree then by previous theorem G has a closed
trail. Otherwise, G has exactly two vertices, u and v of odd degree. In this case, G + e denote
the graph obtained from G by addition of a new edge e joining u and v. Clearly, each vertex of
G + e is even and hence G + e is an Eulerian Graph and contains a Euler line. Hence it contains
an Euler trail.

Theorem 23. A connected graph G is an Euler graph if and only if it can be decomposed into
disjoint cycles(circuits).
Proof: Above theorem can be stated as ”A connected graph G is an Euler graph if and only
if G is the union of some edge disjoint cycles.
Suppose graph G can be decomposed into circuits; that is, G is a union of
edge-disjoint circuits. Since the degree of every vertex in a circuit is two, the degree of every
vertex in G is even. Hence G is an Euler graph.
Conversely, let G be an Euler graph. Consider a vertex v1 . There are at least two
edges incident at v1 . Let one of these edges be between v1 and v2 . Since vertex v2 is also of even
degree, it must have at least another edge, say between v2 and v3 . Proceeding in this fashion,
we eventually arrive at a vertex that has previously been traversed, thus forming a circuit Γ.
Let us remove Γ from G. All vertices in the remaining graph (not necessarily connected) must
also be of even degree. From the remaining graph remove another circuit in exactly the same
way as we removed Γ from G. Continue this process until no edges are left. Hence the theorem.

Definition. A Hamiltonian cycle in a connected graph is defined as a closed walk that traverses
every vertex of G exactly once, except the starting vertex, at which the walk also terminates.

18
Definition. A path which contains every vertex of a connected graph G exactly once is called
Hamiltonian path. A Hamiltonian cycle in a graph G is a closed walk that traverses every
vertex of G exactly once except the starting vertex. A connected graph G is said to be Hamil-
tonian graph if it contains a Hamiltonian cycle.

Since Hamiltonian cycle (or path) traverses every vertex exactly once. Hence it
cannot include a self-loop or a set of parallel edges. Hence we need to consider simple graphs
only for study of Hamiltonian graphs. e.g. a complete graph with more than two vertices is
Hamiltonian, every cycle graph is Hamiltonian.

Note: Every graph that has a Hamiltonian circuit also has a Hamiltonian path. There are,
however, many graphs with Hamiltonian paths that have no Hamiltonian circuits. In contrast
with the case of Euler graphs, no nontrivial necessary and sufficient condition for a graph to
be Hamiltonian is known; in fact, the problem of finding such a condition is one of the main
unsolved problems of the graph theory.

Q. Draw a graph that has a Hamiltonian path but does not have a Hamiltonian circuit.

Theorem 24. If G is a simple graph with number of vertices n(≥ 3) and if d(v) + d(w) ≥ n for
every pair of non-adjacent vertices v and w, then G is Hamiltonian.

Proof: On contrary, let us assume that there exists a non Hamiltonian graph with n vertices
satisfying the given condition for every pair of non adjacent vertices v and w. Let G be such
a maximal non Hamiltonian graph. Since G is maximal non Hamiltonian, it follows that there
exist two non adjacent vertices v and w is G such that addition of an edge joining v and w will
result in a Hamiltonian graph. Hence, G contains a Hamiltonian path.
Consider the figure below

Let S = {vi : is adjacent to vertex v in G and 1 ≤ i ≤ n}

T = {vi : vi−1 is adjacent to vertex w in G and 1 ≤ i ≤ n}
Clearly, |S| = d(v) and |T | = d(w) in G.

Claim: S ∩ T = 0/ and |S ∪ T | ≤ n − 1.

For if, vk ∈ S ∩ T , then the edges (v, vk ) and (vk−1 , w) would be in G and then (v =)v1 v2 ...........
....vk−1 vn (= w)vn−1 .......vk v1 would form a Hamiltonian cycle in G, which is a contradiction.
Further S ∪ T ⊂ {v1 , v2 , ........, vn }. But since vertex v1 = v is neither adjacent to v nor adjacent
to w, v1 ∈/ S ∪ T.
Hence, |S ∪ T | ≤ n − 1

19
Now, we have

d(v) + d(w) = |S| + |T |

= |S ∪ T | { asS ∩ T = 0/
≤ n − 1.

which is a contradiction. Hence G is Hamiltonian.

Corollary 2. If G is a simple graph with number of vertices n(≥ 3) and if d(v)) ≥ n/2 for each
vertex v, then G us Hamiltonian.

Definition. A graph G is said to be planar if there exists some geometric representation of G

which can be drawn on a plane such that no two of its edges intersect. A graph that cannot be
drawn on a plane without a crossover between its edges is called nonplanar.
Definition. A plane representation of planar graph G divides the plane into regions. A region
(also called faces or meshes) is characterized by the set of edges forming its boundary. A region
is finite if the area it encloses is finite otherwise infinite. Two regions are said to be adjacent
if they have a common edge between them.
Definition. A face f is said to incident with the vertices and edges in its boundary. If e is a cut
edge in the plane graph, just one face is incident with e; namely infinite face. We say that an
edge separates the faces incident with it. The degree dG ( f ), of a face f is the number of edges
with which it is incident i.e. number of edges in boundary of face f , cut edges being counted
twice.

Definition. Dual Graph: Given a plane graph G, dual graph of G denoted as G∗ is defined as
follows: corresponding to each face f of G there is a vertex f ∗ of G∗ and corresponding to each
edge e of G there is an edge e∗ in G∗ ; two vertices f ∗ and g∗ are joined by the edge e∗ in G∗ if
and only if their corresponding faces f and g are separated by the edge e in G. The graph G∗ is
called the dual of graph G.

Figure 15: Dual Graph

Note: Dual of a planar graph is also planar. Also, if e is a loop of G, then e∗ is a cut edge
of G∗ and vice-versa. Similarly we can consider the dual of dual i.e. G∗∗ of G∗ and when G is
connected , G∗∗ ∼
= G.
The following are the direct consequences of the definition of G∗

• no. of vertices in G∗ = no. of faces in G

20
 • no. of edges in G∗ = no. of edges in G

• dG∗ ( f ∗ ) = dG ( f )

Theorem 25. If G is a plane graph, then ∑ d( f ) = 2e; where F is the set of faces of G.
f ∈F

Proof: Let G∗ be the dual of G. Then

∑ d( f ) = ∑ d( f ∗ )
f ∈F f ∈V (G∗ )
∗

∗
= 2e(G )
= 2e(G)

Note: 2e ≥ 3 f , as each region is bounded by at least three edges and each edge belongs to
3
exactly two regions, hence e ≥ f .
2

Theorem 26. ( Euler’s Formula) A connected planar graph with n vertices and e edges has
e − n + 2 regions.

Proof: Let G be a connected planar graph. Proof by induction on the number of edges of
G.
If e = 1 then n = 1 or 2, then clearly the result holds.
Let us assume that the result holds for all connected planar graphs with at most e − 1 edges.
Let G be a connected graph with e edges and f regions. If G is a tree then e = n − 1
and f = 1 as only one region (infinite region). Hence the formula f = e − n + 2 holds in this
case.
If G is not a tree then it has some cycles. Let a be an edge in some cycle. Removal
of the edge a from the plane representation of G will merge the two regions into one region.
Thus G − a is a connected graph with n vertices, e − 1 edges and f − 1 regions (where f is the
number of regions in G). By induction hypothesis, we have

f − 1 = (e − 1) − n + 2
=⇒ f = e − n + 2.

Corollary 3. In any simple, connected planar graph with f regions, n vertices, and e edges
such that e > 2, the following inequalities must hold:

• e ≤ 3n − 6.
3
Proof: Now substituting f = e − n + 2 in e ≥ f , we obtain e ≤ 3n − 6.
2
Q. Show that the Peterson graph K5 and K3,3 are non planar.
Solution: In the case of K5 , the complete graph of five vertices n = 5, e = 10 but 3n − 6 = 9
hence e  3n − 6. Hence K5 is non planar.

21
 In case of K3,3 we have n = 6, e = 9, hence the result e ≤ (3n − 6) holds. To prove
the nonplanarity of K3,3 , we make use of the additional fact that no region in this graph can be
bounded with fewer than four edges. Hence, if this graph were planar, we would have 2e ≥ 4 f .
Using the Euler’s formula f = e − n + 2 = 5 in 2e ≥ 4 f we have 18 ≥ 20, a contradiction.
Hence K3,3 is non planar.

Definition. A k-vertex colouring of a graph G is an assignment of k colours 1, 2, 3, ..........., k

to the vertices of G. The colouring is said to be proper if no two distinct adjacent vertices have
the same colour. G is said to be k vertex colourable or k colourable if G has a proper k ver-
tex colouring. Clearly, a graph is k colourable if and only if its underlying simple graph is k
colourable.

Definition. A graph G that requires k different colors for its proper coloring, and no less, is
called a k-chromatic graph, and the number k is called the chromatic number of G. Chro-
matic number of G is denoted by χ(G).

• Chromatic number of a null graph is 1.

• Chromatic number of complete graph Kn of n vertices is n, as all its vertices are adjacent.

• Chromatic number of a graph having one or more edges is atleast two.

Q. Define Chromatic number and find the chromatic number of the following graph.

Figure 16:

Theorem 27. Every tree with two or more vertices is 2-chromatic.

Proof: Let T be a given tree with two or more vertices. Let us choose a vertex v in the tree
T . Paint v with color 1 and paint all vertices adjacent to v with color 2. Next, paint the vertices
adjacent to these (those that just have been colored with 2) using color 1. Continue this process
till every vertex in T has been painted.
Since there is one and only one path between any two vertices is a tree hence no two
adjacent vertices have the same colour. Thus T has been properly coloured with two colours.
Since T has atleast two vertices, it will have atleast one edge. Hence one colour would not be
enough. Thus T is 2 chromatic.

22
Note that the converse of the above theorem is not necessarily true, as a cycle with even number
of vertices is 2 chromatic.

Theorem 28. A graph with at least one edge is 2-chromatic if and only if it has no cycles of
odd length.
Proof: Let G be a connected graph with cycles of only even lengths. Select any vertex v,
paint v with color 1 and paint all vertices adjacent to v with color 2. If a vertex is painted with
colour 2 then any vertex adjacent to it will be painted with colour 1. Since every cycle has even
length, no two vertices will have the same colour. Hence, G is 2-chromatic.

Conversely, if G has a cycle of odd length, we would need at least three colors
just for that cycle. Hence the theorem.

Theorem 29. If ∆ is the maximum degree of the degree of the vertices in a graph G, then
χ(G) ≤ 1 + ∆.
Proof: Let G be a graph with n vertices. We shall prove the result by induction on the
number of vertices. If G has 1 or 2 vertices then the result is clearly true. We assume that
the result is true for all graphs having less than n vertices. Remove any vertex v and all edges
incident on v . Then G − v is a graph with n − 1 vertices and maximum degree of any vertex in
G − v is at most ∆. Hence by induction hypothesis, χ(G − v) ≤ 1 + ∆.
Now we add the vertex v and all edges incident on v to G − v. Since degree of v is
∆, atmost ∆ colours are needed to colour all vertices adjacent to v. We can assign a different
colour to v from ∆ + 1 colours. Hence χ(G) ≤ 1 + ∆.

Q. Show that every simple planar graph having n vertices (n ≥ 3) has a vertex of degree at
most 5.
solution: Let G be a planar graph. Assume that all vertices of G have degree greater than or
equal to 6. Also, we know that the sum of the degrees of all verticies of a graph is equal to
twice the number of edges. Let v and e denote the number of vertices and number of edges
respectively. Then, we have

6v ≤ 2e
3v ≤ e (3)

Since G is given to be a planar graph, then from corollary 3, it must satisfy

e ≤ 3v − 6 (4)

From (3) and (4), we get

3v ≤ e ≤ 3v − 6 (5)

which is not possible. Hence our assumption must be wrong. Hence every planar graph has a
vertex of degree at most 5.

23
Theorem 30. Five Colour Theorem: The vertices of every planar graph can be properly col-
ored with five colors.

Proof: Proof by induction on number of vertices of graph G.

If the number of vertices n in a graph is less than or equal to 5 then we can

properly colour these vertices with five colours. Hence the result holds.

We assume that the result holds for all planar graphs having less than n ver-
tices. Now consider a planar graph with n vertices. Then it must have a vertex v with degree
5 or less. Let G0 = G −v, the graph obtained from G be deleting vertex v. Then by induction
hypothesis, G0 having n − 1 vertices requires no more than five colours. Paint the vertices of
G0 using five colours and now add to it the vertex v along with all edges incident on v. If the
degree of v is less than 4, we can assign a proper colour to v and obtain a proper colouring of
G.

This leaves only a case when d(v) = 5 and all the five colourd have been
used in colouring the vertices a, b, c, d and e adjacent to v as shown in ”figure 16”.

Figure 17:

Suppose that there is a path in G0 = G − v between vertices a and c colored alternately with
colors 1 and 3, Then a similar path between band d, colored alternately with colors 2 and 4,
cannot exist; otherwise, these two paths will intersect and cause G to be nonplanar.

If there is no path between b and d colored alternately with colors 2 and 4,

starting from vertex b we can interchange colors 2 and 4 of all vertices connected to b through
vertices of alternating colors 2 and 4. This interchange will paint vertex b with color 4 and yet
keep G0 properly colored. Since vertex d is still with color 4, we have color 2 left over with
which to paint vertex v.

Had we assumed that there was no path between a and c of vertices painted
alternately with colors 1 and 3, we would have released color 1 or 3 instead of color 2. And
thus the theorem.
Definition. Directed Graph: A directed graph (digraph) G consists of a set of vertices V =
{v1 , v2 , ...}, a set of edges E =
{e1 , e2 , ...}, and a mapping ψ that maps every edge onto some
ordered pair of vertices vi , v j . A digraph is also referred to as an oriented graph.

24
 Figure 18: Directed Graph

In a digraph an edge is not only incident on a vertex, but is also incident out of a vertex and
incident into a vertex. The vertex vi which edge ek is incident out of, is called the initial vertex
of ek . The vertex v j , which ek is incident into, is called the terminal vertex of ek . An edge for
which the initial and terminal vertices are the same forms a self-loop, such as e5 .

The number of edges incident out of a vertex vi is called the out-degree (or
out-valence or outward demidegree) of vi and is written d + (vi ). The number of edges incident
into vi is called the in-degree of vi and is written as d − (vi ).

Note that
n n
∑ d +(vi) = ∑ d −(vi) (6)
i=1 i=1

Definition. An isolated vertex is a vertex in which the in-degree and the out-degree are both
equal to zero. A vertex v in a digraph is called pendant if it is of degree one, that is, if
d + (v) + d − (v) = 1.
Definition. Two directed edges are said to be parallel if they are mapped onto the same ordered
pair of vertices. Edges e8 , e9 and e10 are parallel, whereas edges e2 and e3 are not.
Definition. Simple Digraphs: A digraph that has no self-loop or parallel edges is called a
simple digraph.
Definition. A complete symmetric digraph is a simple digraph in which there is exactly one
edge directed from every vertex to every other vertex , and a complete asymmetric digraph is
an asymmetric digraph in which there is exactly one edge between every pair of vertices.
Note: A complete asymmetric digraph of n vertices contains n(n − 1)/2 edges, but a com-
plete symmetric digraph of n vertices contains n(n − 1) edges.
Definition. A digraph is said to be balanced if for every vertex vi the in-degree equals the out-
degree; that is, d + (v j ) = d − (v j ). (A balanced digraph is also referred to as a pseudosymmetric
digraph, or an isograph.) A balanced digraph is said to be regular if every vertex has the same
in-degree and out-degree as every other vertex.

25
26
Definition. Weighted Graph: A Weighted Graph is a graph in which a non-negative real num-
ber (called weight) is assigned to each edge.

The Chinese Postman Problem

Problem: A postman starts from his post-office in a town to deliver his letters and returns to
his starting point every day. What route should he take so that he visits each road at least once
and the total distance covered is least?

In graph-theoretical terms the problem is dealt with as follows. We construct a weighted

graph G where each edge represents a street in the postman’s route, each vertex represents a
junction of streets and the weight assigned to each edge represents the length of the street be-
tween junctions. If we define the weight of a tour v0 e1 v2 e2 ...en v0 in G to be the sum of the
weights of its edges, i.e., w(e1 ) + w(e2 ) + ..w(en ), the Chinese postman problem is just that
of finding a Euler line of minimum weight in a weighted connected graph with non-negative
weights.

If the weighted graph G so constructed is Euler then any Euler line of G is a tour of mini-
mum weight since it involves each edge of G once and only once. Thus in practice we may use
Fleury’s algorithm to produce such a tour, i.e., a solution to the CPP. If G is not Euler then any
tour in G has to involve some edges more than once.

27
 Dijkstra Algorithm for Shortest Path in Weighted Graphs

The problem of finding the shortest path from a specified vertex s to another specified vertex
t, can be stated as follows: A simple weighted digraph G of n vertices is described by an n × n
matrix D = [di j ]’ where di j = length (or distance or weight) of the directed edge from vertex i
to vertex j, di j ≥ 0, dii = 0 and di j = ∞ if there is no edge from vertex i to vertex j. It should
be noted that in general di j 6= d ji .

Dijkstra’s algorithm labels the vertices of the given digraph. At each stage in the algorithm
some vertices have permanent labels and others temporary labels. The algorithm begins by
assigning a permanent label 0 to the starting vertex s, and a temporary label ∞ to the remaining
n − 1 vertices. From then on, in each iteration another vertex gets a permanent label, according
to the following rules:

1. Every vertex j that is not yet permanently labelled gets a new temporary label whose
value is given by

min [ old label of j, (old label of i + dij )]0 (7)

where i is the latest vertex permanently labelled, in the previous iteration, and di j is the
direct distance between vertices i and j. If i and j are not joined by an edge, then di j = ∞.

2. The smallest value among all the temporary labels is found, and this becomes the perma-
nent label of the corresponding vertex. In case of a tie, select anyone of the candidates
for permanent labeling.

3. Steps 1 and 2 are repeated alternately until the destination vertex t gets a permanent label.

28