Sri Chandrasekharendra

Saraswathi Viswa
Mahavidhyalaya

Graph Theory
Programme course
4 credits

1
Main field of study
Mathematics

Course offered for

Mathematics, Bachelor´s Programme

Specific information
The course is available every second year

Course overview
This course is an introductory course to the basic concepts of Graph Theory. This
includes definition of graphs, vertex degrees, directed graphs, trees, distances,
connectivity and paths

Prerequisites
Some elementary knowledge of linear algebra, particularly matrix algebra, would be
helpful. In addition, a general experience in mathematics.

Course objectives
 The objective of the course is to introduce students with the
fundamental concepts in graph Theory, with a sense of some its
modern applications.
 They will be able to use these methods in subsequent courses in the
design and analysis of algorithms, computability theory, software
engineering, and computer systems

Intended learning outcomes

2
On successful completion of this course, student should be able to
 understand the basic concepts of graphs, directed graphs, and
weighted graphs and able to present a graph by matrices.
 understand the properties of trees
 understand Eulerian and Hamiltonian graphs.
 apply the knowledge of graphs to solve the real-life problem.

Program Outcomes
The students should be able to
 Solve problems using basic graph theory
 To write precise and accurate mathematical definitions of objects in
graph theory.
 Use definitions in graph theory to identify and construct examples and
to distinguish examples from non-example.
 Determine whether graphs are Hamiltonian and/or Eulerian
 Apply theories and concepts to test and validate intuition and
independent mathematical thinking in problem solving.
 Integrate core theoretical knowledge of graph theory to solve
problems.
 Reason from definitions to construct mathematical proofs
 Model real world problems using graph theory

3
Course content
Unit I
Graphs and Subgraphs – Introduction – Definition and Examples – Degree of a vertex
– subgraphs – isomorphism of Graphs – Ramsey Numbers – Independent sets and
Coverings
Unit-II
Intersection Graphs and Line Graphs – Adjacency and Incidence Matrices –
Operations on Graphs – Degree Sequences – Graphic Sequences
Unit III
Connectedness -Introduction – Walks, Trails, paths, components, bridge, block -
Connectivity
Unit IV
Eulerian Graphs – Hamiltonian Graphs
Unit V
Trees – Characterization of Trees – Centre of a Tree – Planarity – Introduction,
Definition and Properties – Characterization of Planar Graphs – Thickness – Crossing
and Outer Planarity

Course literature
S.Arumugam and S.Ramachandran, “Invitation to Graph Theory”, SCITECH
Publications India Pvt. Ltd., 7/3C, Madley Road, T.Nagar, Chennai - 17

Reference Books

1. S.Kumaravelu, SusheelaKumaravelu, Graph Theory, Publishers, 182, Chidambara

Nagar, Nagercoil-629 002.
2. S.A.Choudham, A First Course in Graph Theory, Macmillan India Ltd.
3. Robin J.Wilson, Introduction to Graph Theory, Longman Group Ltd.
4. J.A.Bondy and U.S.R. Murthy, Graph Theory with Applications, Macmillon,
London.

4
 UNIT – I

Graphs and Sub graphs : Definition and examples of graphs –

degrees – sub graphs – isomorphism – Ramsey numbers –
independent sets and coverings

1.1 DEFINITION AND

EXAMPLES(1).GRAPH

Definition: A graph G consists of a pair (V(G), X(G)) , where V(G)

is a non – empty finite set whose elements are called points or
vertices and X(G) is another set of unordered pairs of distinct
elements of V(G). The elements of X(G) are called lines or edges of
the graph.

If x = {u, v} ∈ X then the line x is said to join of u and v. The

points u and v are said to adjacent if x = u v. We say that the points u
and the line x are incident with each other.

If two distinct lines x and y are incident with a common point then
they are called adjacent lines.

A graph with p points and q lines is called a (p, q) graph.

Note: When there is no possibility of confusion we write V

(G) = V andX (G) = X.

Examples:

Let V = {a, b, c, d} and X = {{a, b},{a, c},{a, d}}.

5
G = {V, X} is a (4, 3) graph. This graph can be represented by a
diagram as shown in Fig.1.1.

6
 a

b c d

Fig. 1.1

In this graph the points a and b are adjacent whereas b and c are non –

adjacent.

2. Let V = {1, 2, 3,4} and X ={{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}.

G = (V, X) is a (4, 6) graph.

This graph is represented by the diagram as shown in Fig.1.2.

4 3

1 2

Fig. 1.2

In this graph the lines {1, 3} and {2, 4} intersect in the diagram and their

intersection is not a point of the graph.

Fig. 1.3 is another diagram for the graph given in Fig. 1.2.
1
4
.
2 3

Fig. 1.3
3. The (10, 15) graph given in Fig. 1.4 is called a Petersen graph.

7
 1
2 a 5
b e
c d
3 4
Fig.1.4
Remark:

The definition of a graph does not allow more than one line joining two
points. Also, it does not allow any line joining a point to itself.

Line joining points to itself is called a loop. Fig.1.5 is a loop.

2 3
Fig.1.5
(2). MULTI GRAPH

Definition: If more than one line joining two vertices are allowed then the
resulting object is called a multi graph. Lines joining the same points are called
multiple lines.

Fig. 1.6 is an example of a multi graph.

2 3

Fig. 1.6

8
(3). PSEUDO GRAPH

Definition: If an object contains multiple lines and loops then it is called a

pseudo graph.

Fig. 1.7 is a pseudo graph.

Fig. 1.7

Note: If G is a (p, q) graph then q ≤ p C 2 and q = p C2 if and only if any two

distinct points are disjoint.

(4).COMPLETE GRAPH

Definition: A graph in which any two distinct points are adjacent is called a
complete graph.

A complete graph with p vertices is denoted by K p.

K1 K2 K3 K4 K5

Fig. 1.8

Note: The number of edges of a complete graph K p is p C 2 .

(5). NULL GRAPH

Definition: A graph G whose edge set is empty is called a null graph or a

totally disconnected graph.

9
Example: G1, G2, G3 and G4 are null graphs.

G1 G2 G3 G4

Fig. 1.9

(6).LABELLED GRAPH

Definition: A graph G is called labelled if its p points are distinguished from

one another by names such as v1, v2, ...,v p .

The graphs given in Fig. 1.1 and Fig.1.2 are labelled graphs and the
graph in Fig. 1.8 is an unlabelled graph.

(7).BIPARTITE GRAPH

Definition: A graph G is called a bigraph or bipartite graph if the vertex set V

can be partitioned into two disjoint subsets V 1 and V2 such that every line of G
joins a point of V1 to a point of V2. (V1, V2) is called a bipartition of G.

(8).COMPLETE BIPARTITE GRAPH

Definition: A graph G is called a complete bipartite graph if the vertex set V

can be portioned into two disjoint subsets V1 and V2 such that every line joining
the points of V1 to the points of V2. If V1 contains m points V2 contains n
points then the complete bigraph is denoted by K m, n.

The complete graph K1, n is called a star for n ≥ 1.

10
Note: The number of points of the complete bigraph Km , n is m + n and the
number of lines is m n.

Example:

K 4,2 K2 , 3 K3 , 3

Fig. 1.10

Problem:

Let V = {1, 2, 3, . . . , n} . Let X = {(i , j) / i , j ∊ V and are relatively prime }.

The resulting graph (V, X) is denoted by G n. Draw G4 and G5.

Solution:

For G4 : V = { 1, 2, 3, 4} and X = { (1,2), (1,3), (1,4), (2, 3), (3, 4)}.

For G5 : V = { 1, 2, 3, 4,5} and X = {(1,2), (1,3), (1,4), (1,5),(2,3), (2,5), (3, 4),
(3, 5), (4, 5)}.

1 2 4

5 3

3 4 1 2

Graph of G4 (Fig. 1.11) Graph of G5 (Fig. 1.12)

1.2. DEGREES

Definition: The degree of a point vi in graph G is the number of lines incident

with vi. It is denoted by d(vi) or deg vi or d G(vi).

11
 A point v of degree 0 is called an isolated point. A point v of degree one is
called an end point.

Note: Loops are counted twice.

Example: Consider the following (4, 5) graph, Fig.1.13.

1 2

3 4

Fig.1.13

d(1) = 2, d(2) = 4, d(3) = 2, d(4) = 2.

Total degrees = 10 = 2 x 5.

Theorem 1.1: The sum of the degrees of the points of a graph G is twice the
number of lines in G. i.e. ∑d (vi ) = 2q.

Proof: Every line of G is incident with two points.

∴ Every line contributes two degrees.

There are q lines in (p, q) graph.

∴∑𝑝𝑖=1 (𝑣𝑖 ) = 2q = 2x (number of lines in G).

Theorem 1.2: In any group G the number of points of odd degree is even.

Proof: Let v1, v2, . . . , v k denote the points of odd degree and w1, w2, . . . , wm

denote the points of even degree in G.

By theorem (1.1), ∑𝑘𝑖=1 𝑑(𝑣𝑖) + ∑𝑚𝑗 =1 (𝑤𝑗 ) = 2 q, which is even.

12
 Also, ∑𝑚
𝑗 =1 (𝑤𝑗 ) is even.

𝑘
∴ ∑ 𝑖=1(𝑣𝑖 ) is even.

But, d(vi ) is odd for each i .

Hence, k is even .

∴ the number of points of odd degree is even.

Definition :( REGULAR GRAPH)

For any graph G, we define

𝛿 (G) = min {d (v) / v ∈ V (G)} and

∆ (G) = max {d (v) / v ∈ V (G)}.

If all points of G have the same degree r then G is called a regular graph of

degree r. Hence, in a regular graph 𝛿 (G) = ∆ (G).

A regular graph of degree 3 is called a cubic graph.

Example(1): Consider the following graph , Fig.1.14.

1 2 3

4 5 6

Fig. 1.14.

d(1) = 3, d(2) = 1, d(3) = 3, d(4) = 3, d(5) = 4, d(6) = 2.

Here, 𝛿 = 1, ∆= 4 ⇒ 𝛿 ≠ ∆ .
∴ The given graph is not regular.

Example (2): Consider the graph as given in Fig.1.2.

13
 Here, d(1) = 3, d(2) = 3, d(3) = 3, d(4) = 3.

∴𝛿 =∆=3 ⇒ the graph is regular.

Example (3):

(i). A null graph is a regular graph of degree 0.

(ii). The complete graph K p is a regular graph of degree (p – 1).

Theorem 1.3: Every cubic graph has an even number of points.

Proof: Let G be a cubic graph with p points.

To show that p is even.

𝑝
∴ ∑ 𝑖=1 (𝑣𝑖 ) = 3p, since G is a cubic graph

We know that, by theorem (1.1), ∑𝑝 (𝑣 ) is an even number.

𝑖=1 𝑖

∴ 3p is even ⇒ p is even.

Hence, every cubic graph has an even number of points.

SOLVED PROBLEMS

Problem (1): Let G be a (p, q) graph all of whose points have degree k or k + 1.

If G has t > 0 points of degree k then show that t = p (k +1) – 2q .

Solution:

Given that G is a (p, q) graph and all of whose points have degree k or k + 1.

Also, given that G has t points of degree k.

∴ the remaining p – t points have degree k + 1.

We know that, ∑𝑝𝑖=1 𝑑(𝑣𝑖 ) = 2q .

14
 i.e. t k + ( p – t) ( k +1) = 2q

⇒ t k + p k – t k +p - t = 2q

⇒ t = p k +p - 2q

⇒ t = p (k +1) - 2q.

Problem (2): Show that in any group of two or more people, there are always
two with exactly the same number of friends inside the group.

Solution:

Construct a graph G by taking the group of people as the set of points

and joining two of them if they are friends.

Then deg v = number of friends of v.

To prove that at least two points of G have the same degree.

Let v1, v2, . . . , vp be the points of G , where p ≥ 2.

Clearly 0 ≤ deg vi ≤ p – 1 for each i.

Suppose no two points of G have the same degree.

Then the degree of points v1, v2, . . . , vp are 0, 1 , 2, . . . , p – 1 in some order.

But, a point of degree (p – 1) is joined to ever other point of G.

Hence, no point can have degree zero. This is a contradiction to the fact
that point of G has degree zero.

Thus, there exist two points of G with the same degree.

15
Problem (3): What is the maximum degree of any point in a graph with p
points?

Solution:

Line is obtained by a selection of any two points from the p points.

∴ Maximum number of lines = pC2 = p (p – 1) / 2.

𝑝
∴ ∑𝑖=1 𝑑(𝑣𝑖 ) = p (p – 1)

∴ d (vi ) ≤ (p – 1)

Hence, the maximum degree of any point in a graph with p points is (p – 1).

Problem (4): Prove that 𝛿 ≤ 2𝑞 ≤ ∆.

𝑝

Solution:

Let G be a (p, q) graph and v1, v2, . . . , vp be the points of G.

We know that, ∑𝑝 (𝑣 ) = 2q .
𝑖=1 𝑖

Also, 𝛿 (G) = min {d (v) / v ∈ V (G)} and

∆ (G) = max {d (v) / v ∈ V (G)}.

∴ 𝛿 ≤ d (vi) ≤ ∆ for all i.

𝑝 𝑝 𝑝
∴ ∑ 𝑖=1 𝛿 ≤ 𝑖=1 𝑑(𝑣𝑖 ) ≤ ∑ 𝑖=1
∑ ∆.

i.e. p𝛿 ≤ 2q ≤ p∆ .

i. e. 𝛿 ≤ 2𝑞 ≤ ∆.
𝑝

16
Problem (5): Let G be a k – regular bigraph with bipartition (V1, V2) and k > 0.
Prove that |V1| = |V2|.

Solution:

Given that G is a k – regular bigraph with bipartition (V1, V2) and k > 0.

We know that, “Every line of G joins a point of V1 to a point of V2”.

∴ ∑𝑣∈𝑉1 (𝑣) = ∑𝑣∈𝑉2 𝑑(𝑣).

Also, d(v) = k for all v ∊ V1 ᴜ V2.

Hence, ∑𝑣∈𝑉1 𝑘 = ∑𝑣∈𝑉2 𝑘.

i.e. k |V1| = k |V2|.

i.e. |V1| = |V2| , since k > 0.

Problem (6): A (p, q) graph has t points of degree m and all other points are of
degree n. Show that (m – n) t + p n = 2 q.

Solution:

Given that G is a (p, q) graph and t points of degree m.

The remaining (p – t) points have degree n.

We know that, ∑𝑣∈𝑉 (𝑣) = 2 q.

i.e. m t + (p - t)n = 2q.

i.e. (m – n) t + p n = 2 q.

Problem (7): Give three examples for regular graph of degree 2.

Solution:

17
Exercises:

1. Give an example of a regular graph degree 0.

2. Give an example of a regular graph degree 1.
3. Give three examples for a cubic graph.
4. If G is a graph with at least two points then show that G contains two
vertices of the same degree.
5. Show that a graph with p points is regular of degree p – 1 iff it is
complete.

1.3 SUBGRAPHS

Definition: A graph H = (V1, X1) is called a subgraph of G ( V, X )

if V1 ⊆ V and X1 ⊆ X.

H is a subgraph of G then we say t hat G is a supergraph of H.

H is called a spanning graph of G if V1 = V.

H is called an induced subgraph of G if H is the maximal subgraph

of G with point set V1.

i.e. if H is an induced subgraph of G then two points are adjacent

in H if and only if they are adjacent in G.

Example (1): Consider the graph G given in Fig. 1.15.

1 5

3 Fig. 1.15

18
 Subgraph , H1 Subgraph, H2

1 5

2 4 4

3 Fig. 1.16

Spanning Subgraph Induced Subgraph

1 5 1 5

2 4 3 4

Fig. 1.17 Fig. 1.18

Example (2): Consider the Peterson graph G given in Fig. 1.4.

2 a 5

b e

c d Fig.1.4

3 4

Subgraph of G Induced subgraph of G Spanning Subgraph of G

1 a 1

2 a 5 b e 2 a 3
c c d b e

Fig. 1.19 Fig. 1.20 d c

3 4
Fig. 1.21

19
REMOVAL OF A POINT

Definition: Let G = (V, X) be a graph and v ∈ V. The subgraph of G

obtained by removing the point v and all the lines incident with v is
called the subgraph obtained by the removal of the point v and is
denoted by G – v.

i.e. If G – v = ( V1 , X1) then V1 = V – { v} and

X1 = { x / x ∈X and x is not incident with v }.

i.e. G – v is an induced subgraph of G.

REMOVAL OF A LINE

Definition: Let G = (V, X) be a graph and x ∈ X. Then G – x = (V, X –{x}) is

called the subgraph of G obtained by the removal of the line x .

i.e. G – x is a spanning subgraph of G which contains all the lines of G

except the line x.

ADDITION OF A LINE

Definition: Let G = (V, X) be a graph. Let u , v be two non adjacent points

of G. Then G + u v = (V, X 𝖴 {u, v}) is called the graph obtained by the
addition of the line u v to G.

i.e. G + u v is the smallest super graph of G containing the line u v.

20
Example:
u u u
v1 v v1 v v1 v

x1
G G – v1 G – x1 G+uv
Fig. 1.22

Theorem 1.4: The maximum number of lines among all p point graph with
𝑝2
no triangles is [ ] , where[𝑥] denotes the greatest integer not exceeding the
4

real number x.

Proof:

The result can be easily verified for p ≤ 4.

For p > 4, we prove by induction separately for odd p and for even p.

Case (1): For odd p.

Clearly the result is true when p = 1 or 3.

Assume that the result is true for p = 2n +1.

To prove the result for p = 2n +3.

Let G be a ( p, q) graph with p = 2 n +3 and has no triangles.

𝑝2
If q = 0, then 0 ≤ [ ].
4

Let q > 0.

∴ There exist two adjacent points in G.

21
 Let u and v be a pair of adjacent points in G.

Consider the subgraph G1 = G – {u , v}.

Then G1 has 2n + 1 points and no triangles.

Hence by induction hypothesis,

(2𝑛+1)2 4𝑛2+4𝑛+1
Lines of G1 is q(G1) ≤ [ ] = [ ]
4 4

= [𝑛2 + 𝑛 + 1] = 𝑛2 + 𝑛.
4

i.e. q(G1) ≤ 𝑛2 + 𝑛 .............................................. (1)

Since G has no triangles, no points of G1 can be adjacent to both u and v

in G ................................................................................................(2)

Maximum number of lines between G1 and u or v is 2n + 1.

Now, lines in G are of three types.

(i). Lines of G1 [ ≤ 𝑛2 + 𝑛 , by (1) ]

(ii). Lines between G1 and { u , v} [≤ 2n + 1 , by (2) ]

(iii). Line u v .

Hence, Line of G , q(G) ≤ q(G1) + (2 n +1) + 1.

≤ 𝑛2 + 𝑛 + 2 n +2

= 𝑛2 + 3𝑛 + 2

4𝑛 2 +12𝑛 +8
=
4

4𝑛 2 +12𝑛 +9−1
=
4

22
 (2𝑛+3)2 1
= -
4 4

(2𝑛+3)2
=[ ]
4

𝑝2
i.e. q (G) ≤ [ ], where p = 2 n + 3.
4

∴ The result is true for all odd p.

Also for p = 2 n + 3, the graph K n +1, k +2 has no triangles and the number
of lines is q = ( n +1)(n +2)

= 𝑛2 + 3𝑛 + 2

4𝑛 2 +12𝑛 +8
=
4

(2𝑛+3)2
=[ ]
4

𝑝2
= [ ].
4

Hence this maximum q is attained.

Case (2): For even p.

Clearly the result is true when p = 2 or 4.

Assume that the result is true for p = 2n .

To prove the result for p = 2n +2.

Let G be a ( p, q) graph with p = 2 n +2 and has no triangles.

Let q > 0.

∴ There exist two adjacent points in G.

23
 Let u and v be a pair of adjacent points in G.

Consider the subgraph G1 = G – {u , v}.

Then G1 has 2n points and no triangles.

Hence by induction hypothesis,

(2𝑛)2 4𝑛2
Lines of G1 is q(G1) ≤ [ ] = [ ] = 𝑛2
4 4

i.e. q(G1) ≤ 𝑛2 ..................................................................... (1).

Since G has no triangles, no points of G1 can be adjacent to both u and

v in G ............................................................................................... (2)

Maximum number of lines between G1 and u or v is 2n.

Now, lines in G are of three types.

(i). Lines of G1 [ ≤ 𝑛2 , by (1) ]

(ii). Lines between G1 and { u , v} [≤ 2n , by (2) ]

(iii). Line u v .

Hence, Line of G is q(G) ≤ q(G1) + (2 n +1).

≤ 𝑛2 + 2 n +1

= 𝑛2 + 2𝑛 + 1

4𝑛 2 +8𝑛 +4
=
4

(2𝑛+2)2
=
4

(2𝑛+2)2
=[ ]
4

24
 𝑝2
i.e. q (G) ≤ [ ], where p = 2 n + 2.
4

∴ The result is true for all even p.

Also for p = 2 n + 2, the graph K n +1, k +1 has no triangles and the

number of lines is q = ( n +1)(n +1)

= 𝑛2 + 2𝑛 + 1

4𝑛 2 +8𝑛 +4
=
4

(2𝑛+2)2
=[ ]
4

𝑝2
= [ ].
4

𝑝2
Thus, for p = 2 n + 2, K n +1, k +1 is a (p , [ ]) graph without triangles.
4

𝑝2
∴ q attained its maximum [ ].
4

Hence the theorem.

1.4 ISOMORPHISM

Definition: Two groups G1 = ( V1, X1) and G2 = ( V2, X2) are said to be
isomorphic if there exists a bijection f :V1 → V2 such that u, v ∈ V1 are
adjacent in G1 if and only if f(u) , f(v) ∈ V2 are adjacent in G2.

If G1 is isomporphic to G2 then we write G1 ≅ G2. The map f is

called an isomorphism from G1 to G2.

Example (1): The two graphs given in Fig. 1. 23 are isomorphic.

25
 G1 G2

u4 u3 v3

v4

u1 u2 v1 v2

Fig. 1. 23

f (ui ) = vi is an isomorphism between two groups G1 and G2 for i = 1, 2, 3, 4 .

Example (2): The two graphs given in Fig. 1. 24 are isomorphic.

G1 G2

u4 v5

u5 u3 v3 v2

u1 u2 v1 v4

Fig.1. 24

f(u1) = v1 , f(u2) = v2 , f (u3) = v3 , f(u4) = v4, f(u5) = v5

i.e. f (ui )= vi is an isomorphism between two groups G1 and G2 for i =1, 2,...,5

Theorem 1.5: Let f be an isomorphism of the group G1 = ( V1, X1) and

G2 = (V2, X2). Let v ∈ V1. Then deg v = deg f (v).

i.e. isomorphism preserves the degree of vertices.

Proof:

Let f be an isomorphism of the group G1 = ( V1, X1) and G2 = (V2, X2).

Given that v ∈ V1.

26
 ∴ a point u ∈ V1 is adjacent to v in G1 if and only if f(u) is adjacent to
f(v) in G2.

Also, f is a bijection.

Hence the number of points in V1 which are adjacent to v is equal to

the number of points in V2 which are adjacent to f(v).

∴ deg v = deg f(v).

Hence isomorphism preserves the degree of vertices.

Remark:

1). Two isomorphic group have the same number of points and the same
number of lines.

2). The converse of the above theorem is not true.

i.e. If the degrees of the vertices of two graphs are equal then the
two graphs need not be isomorphic.

Example:

Consider the two graphs given in Fig. 1.25.

u6 v5

u1 u2 u3 u4 u5 v1 v2 v4 v3 v6

G1 Fig. 1.25 G2

Here, deg ui = deg vi for i = 1, 2, 3, 4, 5, 6.

But G1 and G2 are not isomorphic, because u2 is adjacent to u3 in G1 but v2 is

not adjacent to v3 in G2.

27
AUTOMORPHISM

Definition: An isomorphism of a group onto itself is called an

automorphism of G.

Remark:

The set of all automorphism of G is a group. This group is denoted by

Γ(G) and is called the automorphism group of G.

COMPLEMENT

Definition: Let G = ( V, X) be a group. The complement 𝐺̅ of G is defined

to be the graph which has V as its set of points and two points are
adjacent in 𝐺̅ if and only if they are not adjacent in G.

The graph G is said to be a self complementary graph if G is

isomorphic to 𝐺̅ .

Example:

The graphs given in Fig. 1.26 and Fig. 2.27 are self complementary graphs.

u4 u3 v1 v2

u1 u2 v3 v4
G 𝐺̅
Fig. 1.26

28
 u4 v5
u5 u3 v3 v2

u1 u2 v1 v4
G 𝐺̅
Fig. 1. 27
ULAM’S CONJECTURE

Let G and H be two graphs with p points where p > 2 . Let v1, v2, ... ,vp
be the points of G and w1, w2, ..., wp be the points of H. If for each i the
subgraphs Gi = G – vi and H i = H – wi are isomorphic then the graphs G
and H are isomorphic.

Ulam‟s Conjecture is also known as reconstruction conjecture.

SOLVED PROBLEMS:
Problem 1: Prove that any self complementary graphs has 4 n or 4n + 1
points.

Solution:
Let G be a complementary graph with p points.
∴ G ≅ 𝐺̅ .

⟹ |𝑋(𝐺̅)| = |𝑋(𝐺̅)| .

Also, |(𝐺̅)| + |𝑋(𝐺̅)| = Number of edges in K p .

𝑝 (𝑝−1)
= (2) = 2
.

𝑝(𝑝−1)
i.e. 2 |(𝐺̅)| = .
2

29
 (𝑝−1)
⟹ |𝑋(𝐺̅)| = is an integer.
4

i.e. p (p -1) = 4 n, where n ∈ Z.

i.e. p or (p – 1) is a multiple of 4.

⟹ p=4n or p – 1 = 4 n.

i.e. p = 4 n or p = 4 n + 1.

Hence, G has 4 n or 4 n + 1 points.

Problem 2: Prove that Γ(G) = Γ(𝐺̅).

Solution:

We know that, Γ(G) is a group automorphism of G.

First, we prove that, Γ(G) ⊆ Γ (𝐺̅).

Let f ∊ Γ(G) ⟹ f : G → G is an isomorphism.

Let u , v ∊ V(G).

Now, u , v are adjacent in 𝐺̅ ⇔ u , v are not adjacent in G.

- f( u) , f (v) are not adjacent in G ,

since f is an automorphism of G.

- f( u) , f (v) are adjacent in 𝐺̅.

∴ f : 𝐺̅ → 𝐺̅ is an automorphism.

∴ f ∊ Γ(𝐺̅).

Hence, Γ(G) ⊆ Γ (𝐺̅).

30
Similarly, we can prove that Γ (𝐺̅) ⊆ Γ(G).

∴ Γ(G) = Γ(𝐺̅).

Exercises:

1. Show that isomorphism is an equivalent relation among graphs.

2. Prove that any group with p points is isomorphic to K p.
3. Give a self complementary graph having five vertices.
4. Show that the graphs given in Fig. 1.28 are not isomorphic.

Fig. 1.28

5. Find the complements of the graph given in Fig. 1.24.

1.5 RAMSEY NUMBER

Consider the following puzzle. In any set of six points there will
always be either a subset of three who are mutually acquainted, or a
subset of three who are mutually strangers. This situation may be
represented by a graph G with six points representing the six people in
which adjacency indicates acquaintances. The above puzzle asserts that G
contains three mutually adjacent points or three mutually non – adjacent
points. That is G or 𝐺̅ contains a triangle.

Theorem 1.6: For any graph G with 6 points, G and 𝐺̅ contains a triangle.

Proof:

Let G be a group with 6 points.

31
 Let v be a point of G.

Since G contains 5 points other than v , v must be either adjacent to

three points in G or non – adjacent to three points in G.

Hence v must be adjacent to three points in G or in 𝐺̅.

Without loss of generality, let us assume that v is adjacent to three points

u1, u2, u3 in G.

If two of these three points are adjacent then G contains a triangle.

Otherwise these three points form a triangle in 𝐺̅.

Hence G or 𝐺̅contains a triangle.

Note: The above theorem is not true for graphs with less than six points.

RAMSEY NUMBER:

Ramsey number is the least positive integer r (m, n) such that for any
group G with r (m, n) points , G contains Km or 𝐾𝑛.

Example: r (3, 3) = 6

r (1, k) = r (k, 1) = 1 for any positive integer k.

SOLVED PROBLEMS:

Problem 1: Prove that r (m, n) = r (n, m).

Solution:

Let r (m, n) = s.

Let G be any group with s points. Then 𝐺̅ also has s points.

Since r (m, n) = s , 𝐺̅ contains Km or 𝐾𝑛. .

32
  G contains 𝐾𝑚. or Kn .

i.e. G contains Kn or 𝐾𝑚 .

Thus an arbitrary graph on s points contains K n or 𝐾𝑚 as an

induced subgraph.

 r (m, n) ≤ r (n, m) ………(1).

Interchanging m and n, we get

r (n, m) ≤ r (m, n) ………(2).

Hence from (1) and (2),

r (m, n) = r (n, m).

Problem 2: Prove that r (2, 2) = 2

Solution:

Let G be a graph with 2 points.

Let the two points be u and v.

Then u and v are either adjacent in G or adjacent in 𝐺̅.

i.e. G or 𝐺̅. contains K2.

Thus if G is any graph on two points then G contains K2 or 𝐾

2.

Clearly 2 is the least positive integer with this property.

 r (2, 2) = 2.

Exercises:

1. Prove by suitable example that the theorem 1.6 is not true for graphs
with less than 6 points.
2. Find r (1, 1) .

33
 3. Find r (2, 3).
4. Find r (2, k) for any positive integer k .

1. 6 INDEPENDENT SETS AND COVERINGS

INDEPENDENCE SET

Definition: Let G = (V, X) be a graph. A subset S of V is called an

independent set of G if no two vertices of S are adjacent in G.

An independent set S is said to be maximum if G has no

independent set S1 with │S1│ > │S│.

The number of vertices in a maximum independent set is called

the independent number of G and is denoted by α .

Example: Consider the graph given in Fig. 1.29.

v4

v5 v3

v1 v2

Fig. 1.29

S1 = { v1 , v3, v4} , S2 = { v2 , v5 }, S3 = { v3, v4 } are independent

sets.

S1 is the maximal independent set .

 α = │S1│ = 3.

34
VERTEX COVERING

Definition: A covering of a graph G = (V, X) is a subset K of V such

that every line of G is incident with the vertex in K.

A covering K is called a minimum covering if G has no

covering K1 with │ K1│ < │ K│.

The number of vertices in a minimum covering of G is called the

covering number of g and is denoted by β.

Example: Consider the graph given in Fig. 1. 29.

K1 = { v1 , v3, v4} , K2 = { v2 , v5 } , K3 = { v4 ,v2 , v5 } are covering of G.

K2 is the minimum covering.

β = │ K2│ = 2

Theorem 1.7: A set S ⊆ V is an independent set G if and only if V - S is

a covering of S.

Proof:

Let G = (V, X) be a graph.

By definition, A set S ⊆ V is an independent iff no two vertices of S are

adjacent.

i.e. iff every line of S is incident with at least one point of V - S.

i.e. iff V - S is a covering of G.

Corollary 1.1: For any graph G of p vertices α + β = p

Proof: Let G be a group with p vertices.

Let S be a maximum independent set and K be a minimum covering of G.

35
  │S│ = α and │K│ = β.

By theorem 1.7, S is an independent set iff V – S is an covering.

But, K is a minimum covering of G.

Hence, │K│ ≤ │V – S│.

i.e. β ≤ p - α

i.e. β + α ≤ p ...................................... (1)

Also K is a covering iff V – K is an independent set.

But, S is a maximum independent set.

 │V – K│ ≤ │S│.

i. e. p – β ≤ α

i. e. p ≤ α + β ..................................... (2)

From equations (1) and (2), we get α + β = p.

LINE COVERING

Definition: A line covering of a graph G = (V, X) is a subset L of X

such that every vertex is incident with a line of L.

The number of lines in a minimum line covering of G is called the

line covering number of G and is denoted by β1.

A set of lines is called independent if no two of them are adjacent.

The number of lines in a maximum independent set of lines is called

the edge independent number and is denoted by α1.

36
Example: Consider the graph of Fig.1. 30.

x4 x3

x6 x9

x5 x7 x8 x2

x1

Fig.1.30

L1 = { x1, x3, x6 } , L2 = { x2, x4 }, L3 = { x3, x5, x8 } are edge independent

sets.

Here, L1 and L3 are maximum edge independent sets.

 α1 = │L1│= │L3│= 3.

K1 = { x1, x3, x6 } and K2 = { x3, x5, x8 } are edge covering sets.

i.e. K1 and K2 are minimum edge covering sets.

 β1 = │K1│= │K2│= 3.

GALLIA’S THEOREM

Theorem 1.8: For any non – trivial graph with p vertices, α1 + β1 = p.

Solution:

Let G be a (p, q) graph.

We know that, α1 is the maximal edge independent set and β1 is the

minimum edge covering number.

Let S be the maximum independent set of lines of G.

37
  │S│ = α1.

Let M be a set of lines, one incident line for each of the p - 2 α1 points
of G not covered by any line of S.

Clearly, S U M is a line covering of G.

 │S U M│ ≥ β1

i.e. α1 + p - 2 α1 ≥ β1

i.e. p ≥ α1 + β1 .....................................(1).

Let T be the minimum edge covering set.

 │T│ = β 1.

T cannot have a line x , both of whose ends are also incident with lines
of T other than x.

Hence G[T], the spanning subgraph of G induced by T is the union of

stars.

Hence each line of T is incident with at least one end point of G [T].

Let W be the set of end points of G [T] consisting of exactly one

end point for each line of T.

 │W│ = │T│ = β 1

Hence, p = │T│ + number of stars in G [T]

i.e. p = β 1 + number of stars in G [T] .................. (2)

By choosing one line from each star, we get a set of independent lines.

 α1 ≥ (number of stars in G[T])

38
 i.e. p ≤ β 1 + α1 ......................................................... (3)

Hence, from equations (1) and (3), α1 + β1 = p.

SOLVED PROBLEMS:

Problem 1: Find α, β, α1 and β1 for the complete graph K p.

Solution:

K2

v1 x1 v2 α = 1, β = 1

α1 = 1, β1 = 1

v3

x3 x2 α = 1, β = 2

v1 x1 v2 α1 = 1, β1 = 2

v4 x3 v3 α = 1, β =3

x4 x5 x6 x2 α1 = 2, β1 = 2

v1 x1 v2

v4

x4 x6 x7 x3 α = 1, β = 4

v5 x8 v3 α1 = 2, β1 = 3

x5 x9 x10 x2

v1 x1 v2

39
 v5 v4

v6 v3 α = 1, β = 5

α1 = 3, β1 = 3

v1 v2

Fig.1.31

α = 1, β = p – 1

𝑝
1 2
𝑖𝑓 𝑝 𝑖𝑠 𝑒𝑣𝑒𝑛
α = { 𝑝−1 and β1 = p - α1.
2
𝑖𝑓 𝑝 𝑖𝑠 𝑜𝑑𝑑

Problem 2: Give an example to show that the complement of an

independent set of lines need not be a line covering.

Solution: Consider the graph given in fig. 1.32.

x4

x5 x3 x2

x1

Fig.1.32

Independent set, S = { x2 , x5}

Complement of independent set, S1 = { x1 , x3, x4}.

Exercises:

1. Give an example to show that the complement of a line covering

need not be an independent set of lines.

40
 2. Prove or disprove. Every covering of a graph contains a minimum
covering.
3. Prove or disprove. Every independent set of lines is contained in a
maximum independent set of lines.

Unit II
Intersection graphs and line graphs – matrices – operations in graphs – degree
sequences, graphicsequences.
INTERSECTION GRAPHS

Definition: Let F = {S1 , S2, …, S n } be a non - empty family of distinct

non – empty subsets of a given set S. The intersection graph of F, denoted by
Ω (F) is defined as follows:

The set of points V of Ω (F) is F itself and two points Si , Sj are

adjacent if i ≠ j and Si ∩ Sj ≠ φ .

A graph G is called an intersection graph on S if there exists a

family F of subsets of S such that G is isomorphic to Ω (F).

Example:

Let S = { a, b, c } and

F = { {a} , {c} , { a , b} , {b, c}} = { A , B, C, D } , say.

𝛀 (F)

A B

C D

Fig.2.1

41
Theorem 2.1: Every graph is an intersection graph.

Proof:

Let G = (V, X) be a graph.

Let the vertex set V = {v1, v2, …, vp}.

Let S = V U X.

For each vi ∊ V, we define

Si = {vi} U { x ∊ X / the edge x is incident on vi}.

Clearly, F = {S1, S2, …, Sp} is a family of non – empty subsets of S.

To prove that G is an intersection graph.

i.e. to prove G ≅ Ω (F).

Now, If vi and vj are adjacent in G then x = vi vj ∊ Si and vi vj ∊ Sj.

⇒ vi vj ∊ Si ∩ Sj

⇒ Si ∩ Sj ≠ φ

⇒ Si and Sj are adjacent in Ω (F).

Conversely, If Si and Sj are adjacent in Ω (F)

⇒ Si ∩ Sj ≠ φ

⇒ The element common to Si and Sj is the line

joining vi and vj.

⇒ vi is adjacent to vj in G .

Thus the map f : V → F defined by f(vi) = Si is an isomorphism of G to

Ω (F) .

42
  G ≅ Ω (F).

Hence, every graph is an intersection graph.

LINE GRAPH

Definition: Let G = (V, X) be a graph with X ≠ φ. Then X is a family of two

element subsets of V. The intersection graph Ω (X) is called a line graph of G
and is denoted by L(G). Thus the points of L(G) are the lines of G and
two points in L(G) are adjacent iff the corresponding lines are adjacent
in G.

Example: Consider the graph given in Fig. 1.34.

w x1 x2

x2

u x1 v x3 x4 x3

x4
x
G L(G)

Fig.2.2

Theorem 2.2: Let G be a (p , q) graph .Then L(G) is a ( q , q L ) graph

where q = 1 (∑𝑝 𝑑2) - q , where d is the degree of the vertex v in G.

L 2 𝑖=1 𝑖 i i

Proof:

Let G be a (p , q) graph.

By the definition of line graph,

Number of points in L(G) is the number of lines in L(G).

43
  L(G) has q points.

Also, di is the degree of the vertex vi in G.

But, Any two of the di lines incident with vi are adjacent in L(G).

𝑑𝑖 (𝑑𝑖−1)
 lines in L(G) .
2

𝑝 𝑑𝑖 (𝑑𝑖−1)
Hence, q L = ∑𝑖=1
2
1
= (∑𝑝 𝑑2) - 1 (∑𝑝 𝑑 )
2 𝑖=1 𝑖 2 𝑖=1 𝑖

= 1 (∑𝑝 𝑑2) - 1 (2𝑞)

2 𝑖=1 𝑖 2

= 1
(∑𝑝 𝑑2) - q
2 𝑖=1 𝑖

Definition:A graph G is called a line graph if G ≅ L(H)for some graph H.

Example: Consider the graph given in Fig. 2.2.

Clearly, K4 - x is a line graph.

MATRICES

ADJACENCY MATRIX

Definition: Let G = (V, X) be a (p, q) graph. Let V = {v1, v2, …,v p}. The p x p
matrix A = (a i j) where

a ij = 1 , if vi is adjacent to v j

0 , otherwise

is called the adjacency matrix.

44
Example: The adjacency matrix of the graph G given in Fig. 1.35 is shown
below:

v1 G
x1 x4
v2 x5 v3 x6 v4
x2 x3

v5 Fig. 1.35

Adjacency Matrix

v1 v2 v3 v4 v5

v1 0 1 0 1 0

v2 1 0 1 0 1

v3 0 1 0 1 0

v4 1 0 1 0 1

v5 0 1 0 1 0

Remark:

1. The adjacency matrix A is symmetric.

2. The sum of the ith row of A is equal to the degree of vi.
3. The entries along the principal diagonal of A are 0.

INCIDENCE MATRIX

Definition: Let G = (V, X) be a (p, q) graph. Let V = {v1, v2, …,v p} and

X = { x1, x2, …, x q}. The p x q matrix B = (a i j) where

45
 b ij = 1 , if vi is adjacent with x j

0 , otherwise

is called the incidence matrix of the graph.

Example: The incidence matrix of the graph G given in Fig. 1.35 is shown
below:

Incidence matrix

x1 x2 x3 x4 x5 x6

v1 1 0 0 1 0 0

v2 1 1 0 0 1 0

B= v3 0 0 0 0 1 1

v4 0 0 1 1 0 1

v5 0 1 1 0 0 0

Remark:

1. The sum of the ith row of B is equal to the degree of vi.

2. Each column of the incident matrix B contains exactly two 1‟s because
each edge is incident with exactly two vertices.

Exercises:

1. Write the adjacency and incidence matrix for the graph G given in
Fig.1.34.
2. Relabel the points of the graphs given in Fig. 1.30 and Fig. 1.32 and
write the incidence and adjacency matrices for the relabeled graph.

46
OPERATIONS ON GRAPHS

Definition:

Let G1 = (V1, X1) and G2 = (V2, X2) be two graphs with V1 ∩ V2 = φ . Then

(i).The union G1U G2 to be the graph (V, X) where V = V1 U V2 and

X= X1 U X2.

(ii). The sum G1 + G2 as G1U G2 together with all the lines joining points of

V1 to points of V2.

(iii). The product G1  G2 is the graph having vertex set V = V1 V2 and

u = (u1, u2) and v = (v1, v2) are adjacent if u1 = v1 and u2 is adjacent to v2

in G2 or u1 is adjacent to v1 in G1 and u2 = v2.

(iv). The composition G1[G2] is the graph having vertex set V1V2 and

u = (u1, u2) and v = (v1, v2) are adjacent if u1 is adjacent to v1 in G1 or

(u1 = v1 and u2 is adjacent to v2 in G2).

Example:

G1 G2 (G1 U G2) G1 + G2

v1 v1 v1

u1 v2 u1 v2 u1 v2

u2 v3 u2 v3 u2 v3

G1 x G2 G1 [G2]

47
 (u2, v1) (u2, v2) (u2, v3) (u2, v1) (u2, v2) (u2, v3)

(u1, v1) (u1, v2) (u1, v3) (u1, v1) (u1, v2) (u1, v3)

Fig. 2.3

Note: 𝐾𝑚 + 𝐾𝑛 = 𝐾𝑚 ,𝑛 .

Theorem 2.3: Let G1 be a (p1, q1) graph and G2 be a (p2, q2) graph.

(i). G1U G2 is a ( p1 + p2 , q1 + q2) graph.

(ii). G1+ G2 is a ( p1 + p2 , q1 + q2 + p1 p2) graph.

(iii). G1 x G2 is a ( p1 p2 , q1 p2 + q2 p1) graph.

(iv). G1 [G2] is a ( p1 p2 , p1 q2 + 𝑝2 2q1) graph.

Proof:

(i). Let G1 be a (p1, q1) graph and G2 be a (p2, q2) graph.

We know that, G1U G2 is a graph with vertex set V = V1 U V2

and X= X1 U X2.

│V1 U V2│ = p1 + p2 and │X1 U X2│ = q1 + q2.

Hence G1U G2 is a ( p1 + p2 , q1 + q2) graph.

(ii). We know that, G1+ G2 is a graph with vertex set V = V1 U V2.

│V1 U V2│ = p1 + p2 and

Number of lines in G1+ G2 = number of lines in G1U G2 + number of

lines joining points of V1 to the points of V2.

48
 = q1 + q2 + p1 p2.

 G1 + G2 is a ( p1 + p2 , q1 + q2 + p1 p2) graph.

(iii). We know that, G1  G2 is a graph with vertex set V = V1  V2.

│V1  V2│ = p1 p2.

Also we know that, the points (u1, u2) and (v1, v2) are adjacent if u1 = v1
and u2 is adjacent to v2 in G2 or u1 is adjacent to v1 in G1 and u2 = v2.

 deg (u1, u2) = deg u2 + deg u1

i.e. deg (u1, u2) = deg u1 + deg u2.

1
The total number of lines in G  G = [∑𝑝1 𝑝2 𝑑𝑒𝑔(𝑢 , 𝑢 )]
1 2 ∑
𝑖 = 1 𝑗 =1 𝑖 𝑗
2

= 1 [∑𝑝1 ∑p2 (𝑑𝑒𝑔𝑢 + 𝑑𝑒𝑔 )]

2 𝑖 =1 𝑗 =1 𝑖 𝑗
𝑝1 𝑝1
= 1 [∑ p (𝑑𝑒𝑔𝑢 ] + 1 [∑ p2 (𝑑𝑒𝑔𝑢 ]
∑ 2 𝑖 ∑ 𝑗
2 𝑖 = 1 𝑗=1 2 𝑖=1 𝑗=1

= 1 [𝑝 2𝑞 + 𝑝 2𝑞 ]
2 2 1 1 2

= p2 q1+ p1 q2

Thus G1 G2 is a ( p1 p2 , p2 q1+ p1 q2) graph.

(iv). G1[G2] is the graph with vertex set V1V2

│V1  V2│ = p1 p2.

Also, we know that, the points (u1, u2) and (v1, v2) are adjacent in G1[G2]

if u1 is adjacent to v1 in G1 or (u1 = v1 and u2 is adjacent to v2 in G2).

 deg (u1, u2) = deg u2 + p2 deg u1

49
 = p2deg u1 + deg u2

The total number of lines in G1[G2]

1
= [∑𝑝1 𝑝2 𝑑𝑒𝑔(𝑢 , 𝑢 )]
∑
𝑖 = 1 𝑗 =1 𝑖 𝑗
2

= 1 [∑𝑝1 ∑p2 (𝑝 𝑑𝑒𝑔𝑢 + 𝑑𝑒𝑔 )]

2 𝑖 =1 𝑗 =1 2 𝑖 𝑗
𝑝1
= 1 [𝑝 ∑𝑝1 p (𝑑𝑒𝑔𝑢 )] + 1 [∑ p2 (𝑑𝑒𝑔𝑢 )]
2
∑ 2 𝑖 ∑ 𝑗
2 𝑖 = 1 𝑗=1 2 𝑖=1 𝑗=1

= 1 [𝑝22𝑞 + 𝑝 2 ]
2 2 1 1 2

= 𝑝22 q1+ p1 q2

Hence G1 [G2] is a ( p1 p2 , p1 q2 + 𝑝22 q1) graph.

Exercises:

1. What is Km + Kn ?
2. Express K4 – x in terms of K2 and 𝐾
2 .

3. Express the graph G in Fig. 1. 35 in terms of 𝐾3 and 2 .

4. Express the graph L (G) in Fig. 1. 34 in terms of K1 and K3.

DEGREE SEQUENCES

Definition: A partition of a non – negative n is a finite set of non –

negative integers d1, d2, . . . , d p whose sum is n. This partition is denoted
by (d1, d2, . . . , d p).

For example, the integer 5 has the following partitions.

5 = (2, 2, 1) or (4, 1) or (3, 2) or ( 3, 1, 1) or (2, 1, 1) or (1, 1, 1, 1, 1).

50
Definition: Let G be a (p, q) graph. The partition of 2q as the sum of the
degree of its points is called the partition or the degree sequence of the
graph.

Example: Consider the graph K1, 2 given in Fig. 2.4.

v1

v2 v3

Fig. 2.4
Here, d(v1) = 2 , d(v2) = 1 , d(v3) = 1

 degree sequence of K1, 2 = ( 2, 1, 1).

GRAPHICAL PARTITION (OR) GRAPHIC SEQUENCE

Definition: A partition P = (d1, d2, . . . , d p) of n into p parts is said to be

a graphical partition or a graphic sequence if there exists a graph G
whose points have degree d i. G is called a realisation of P.

Example:
The partition P = (2, 1, 1) of 4 is graphical and K1, 2 is the unique
realization of P.

Remarks:
1. Any two isomorphic graphs determine the same partition.
But the converse is not true.
For example , the two non – isomorphic graphs given in
Fig. 1.25 determine the same partition (3, 2, 1, 1, 1).

51
 2. If the partition (d1, d2, . . . , d p) of n is graphical then n is even
and d i ≤ p – 1 for each i.
This is the necessary condition that the sequence (d1, d2, . . . , d p)
to be graphical . However the condition is not sufficient.

SOLVED PROBLEMS

Problem 1: Show that the partition P = (7, 6, 5, 4, 3, 2) is not graphic.

Solution:

Suppose P is graphic.

Then P has realization graph G.

Clearly, G has six points

Hence the maximum degree of any point in G is ≤ 5.

This is a contradiction to the degrees are 6 , 7.

 the given partition is not graphic.

Problem 2: Show that the partition P = (6, 6, 5, 4, 3, 3, 1) is not graphic.

Solution:

Suppose P is graphic.

Let G be its realization graph .

Clearly, G has seven points

Given that two points of G have degree 6.

 These two points are adjacent to every other point of G.

 The minimum degree of each vertex in G is at least 2.

52
 This is a contradiction to the fact that a point has degree 1.

Hence P is not graphic.

Problem 3: Show that the partition P = (7, 6, 5, 4, 3, 2, 1) is not graphic.

Solution:

Suppose P is graphic.

Let G be its realization graph .

Clearly, G has seven points

Then G has seven points and maximum degree is 6.

This is a contradiction to the fact that the degree of a point is 7.

Hence P is not graphic.

GRAPHIC SEQUENCES

Theorem 2.4: [The necessary and sufficient condition for a partition tobe
graphical]

A partition P = (d1, d2, . . . , d p) of an even number into p parts with

p -1 ≥ d1 ≥ d2 ≥ . . . ≥ d p is graphical iff the modified partition 𝑃′ =(d2 -1, . .

. , 𝑑𝑑1+1 − 1, 𝑑𝑑1+2, . . . , d p) is graphical.

Proof:

Assume that the modified partition

𝑃′ =(d2 -1, . . . , 𝑑𝑑1+1 − 1, 𝑑𝑑1+2, . . . , d p) is graphical.

Let 𝐺̅′ be its realisation graph with vertex set {v2,v3, . . . , v p} such that

53
 d (v2) = d2 -1 , d (v3) = d3 -1, . . . , d(𝑣𝑑1+1 ) = 𝑑𝑑1+1, . . . , d (v p) = d p.

Let G be a graph obtained from 𝐺̅′ by adding a new vertex v1 and

making it adjacent to v2, v3, . . . , 𝑣𝑑1+1.

Clearly, the partition of G is (d1, d2, . . . , d p).

Hence P is a graphic sequence.

Conversely, suppose P is graphical.

Let G = (V, X) be a realization graph of P with vertex set

V = {v1, v2, . . . , v p} and deg vi = d i.

If v1 is adjacent to v2, v3, . . . , 𝑣𝑑1+1 then 𝐺̅′ = G – { v1} is a realization

graph of P1.

 𝑃′ =(d2 -1, . . . , 𝑑𝑑 1+1

− 1, 𝑑𝑑 1+2
, . . . , d p)

⇒ the modified partition P1 is graphical.

If v1 is not adjacent to all the vertices v2, v3, . . . , 𝑣𝑑1+1 then there exist
two vertices vi and v j such that d i > d j and v1 is adjacent to v j but not
adjacent to vi.

Since v1 vi is not an edge, there exist a vertex v k such that v k is

adjacent to v i but not adjacent to v j.

Let 𝐺̅′ be the graph obtained from G by deleting the lines v1 v j and
vi v k and by adding the lines v1 v i and v j v k.

Clearly 𝐺̅′ is a realisation of P in which v1 is adjacent to v I but not

with v j.

54
 By repeating this process we get a realisation of P in which v1 is
adjacent to all the vertices v2, v3, . . . , 𝑣𝑑1 +1.

Thus the modified partition 𝑃′ is graphical.

Hence the theorem.

Note:

The above theorem gives an effective algorithm to determine whether

a given partition P is graphical and to obtain a graph G realising P
when it is graphical.

Algorithm:

Let P = (d1, d2, . . . , d p) be a partition of an even integer with

p -1 ≥ d1 ≥ d2 ≥ . . . ≥ d p . P is graphical iff the following procedure results

in

a partition with every summand zero.

1). Determine the modified partition P1 described in theorem 1. 12.

i.e. 𝑃′ =(d2 -1, . . . , 𝑑𝑑 1+1 − 1, 𝑑𝑑 +2

1
, . . . , d p)

2). Reordering the terms of 𝑃′ so that they are non – increasing and call

the resulting partition P1.

3). Determine the modified partition 𝑃′′ of P1 and let P2 be the

reordered partition.

4). Continue this process as long as non – negative summands can be

obtained.

55
SOLVED PROBLEMS

Problem 1: Prove that the partition P = (6, 6, 5, 4, 3, 3, 1) is not graphical.

Solution:

Given partition is P = (6, 6, 5, 4, 3, 3, 1).

= (d1, d2, d3, d4, d5, d6, d7)

d1 = 6, 𝑑𝑑1+1 = 𝑑6+1 = 𝑑7 , 𝑑𝑑1+1 − 1 = 𝑑7 - 1 = 1 -1 = 0

The modified partition is

𝑃′ = (d2 -1, . . . , 𝑑𝑑 1+1

− 1, 𝑑𝑑 1+2
, . . . , d p).

= ( 5, 4, 3, 2, 2, 0).

𝑃′′ = (3, 2, 1, 1, -1).

It contains the negative number.

 𝑃′′ is not graphical.

 P is not graphical.

Problem 2: Prove that the partition P = (4, 4, 4, 2, 2, 2) is graphical and

construct graphs realizing the partition.

Solution: Let P = (4, 4, 4, 2, 2, 2) .

The modified partition is 𝑃′ = (d2 -1, . . . , 𝑑𝑑 1+1

− 1, 𝑑𝑑 1+2
, . . . , d p).

= ( 3 , 3, 1, 1, 2) , since 𝑑𝑑1+1 − 1 = d5 -1 = 2 – 1 =1

= (v2, v3, v4, v5, v6) , say

P1 = (3, 3, 2, 1, 1) = (v2, v3, v6 , v4, v5)

56
 𝑃1′ = (2, 1, 0, 1) = (v3, v6 , v4, v5)

P2 = (2, 1, 1, 0) = (v3, v6 , v5, v4)

Realisation of graph P2:

v4

v3 v6

v5 Fig. 2.5

Realisation of graph P1:

v2 v4

v3 v6

v3 Fig. 2.6

Realisation of graph P:

v1

v2 v4

v3 v6

v5 Fig. 2.7

P2 is graphical

 P1 is graphical

Hence, P is graphical.

Problem 3: Which of the following partitions are graphical? Wherever

graphical, construct graphs realizing the partitions.

(a). (5, 5, 3, 3, 2, 2)

57
(b). (5, 3, 2, 1,1, 1,1,1,1)

( c). (7, 6, 5, 4, 3, 3, 2)

(d). (4, 3, 2, 1, 1, 1)

(e). (5, 3, 3,3, 3, 3)

Solution:

(a). Partition P = (5, 5, 3, 3, 2, 2) = (v1, v2, v3, v4, v5, v6 )

Modified partitions

𝑃′ = (4, 2, 2, 1, 1) = (v2, v3, v4, v5, v6 )

𝑃′′ = (1, 1, 0, 0) = (v3, v4, v5, v6 )

Realisation of 𝑃′′ : Realisation of 𝑃′ :

v4 v2

v3 v5 v3 v4

v6 v6 v5

Realisation of :

v2 v1

v3 v4

v6 v5

𝑃′′ is graphical.

 𝑃′ is graphical.

Hence, P is graphical.

58
(b). Let P = (5, 3, 2, 1,1, 1, 1, 1, 1) = (v1, v2, v3, v4, v5, v6 , v7, v8, v9)

𝑃′ = ( 2, 1, 0, 0, 0, 1, 1, 1) = (v2, v3, v4, v5, v6 , v7, v8, v9)

P1 = ( 2, 1, 1, 1, 1, 0, 0, 0) = (v2, v3, v7, v8, v9, v4, v5, v6)

𝑃1′ = (0, 0, 1, 1, 0, 0, 0) = (v3, v7, v8, v9, v4, v5, v6)

P2 = ( 1, 1, 0, 0, 0, 0, 0, 0) = (v8, v9, v3, v7, v4, v5, v6)

Realisation of P2: Realisation of P1

v3 v3 v2

v4 v6 v7 v4 v6 v7

v5 v8 v5 v8

v9 v9

Realisation of P:

v1

v3 v2

v4 v6 v7

v5 v8

v9

P2 is graphical

 P1 is graphical.

Hence, P is graphical.

59
(c) Let P = (7, 6, 5, 4, 3, 3, 2)

Suppose P is graphical

Let G be its realization graph. Then G contains 7 points and the

maximum degree is 6.

This is a contradiction, since here the degree is 7.

 P is not graphical.

Theorem 2.6: If a partition P = (d1, d2, . . . , d p) with d1 ≥ d2 ≥ . . . ≥ d p

is graphical then ∑𝑝 𝑑 is even and ∑𝑝 𝑑 ≤ k (k – 1) + ∑𝑝 𝑚𝑖𝑛{𝑘, 𝑑 }
𝑖=1 𝑖 𝑖=1 𝑖 𝑖=𝑘+1 𝑖

for 1 ≤ k ≤ p.

Proof:

Given that the partition P = (d1, d2, . . . , d p) is graphical.

Let G = (V , X) be the realization of P with vertex set V = {v1, v2,…, v p}

and deg vi = d i .

We know that, by theorem 1.1

𝑝
∑𝑖=1 𝑑𝑖 = 2 q = even number.

𝑝
 ∑ 𝑖=1 𝑑𝑖 is even.

Now the sum ∑𝑝𝑖=1 𝑑𝑖 is the sum of the degrees of the vertices v1,v2,…, v k.

This can be divided into two parts.

The first part contains the lines joining the points v1, v2,…, v k.

This part is ≤ k (k – 1).

The second part contains lines joining one of the points

60
 { 𝑣𝑘+1 , 𝑣𝑘+2 ,…, 𝑣𝑝 } with the points on the set { v1, v2,…, v k}.

Clearly the second part is ≤ ∑𝑝 𝑚𝑖{𝑘, 𝑑 }

𝑖=𝑘+1 𝑖

Hence, ∑𝑝𝑖=1 𝑑𝑖 ≤ k (k – 1) + ∑𝑖=𝑘+1

𝑝
𝑚𝑖𝑛{𝑘, 𝑑𝑖 }.

61
 UNIT – III

Walks - trails and Paths - connectedness and components - blocks -

connectivity

WALKS, TRIALS AND PATHS

WALK

Definition: A walk of a graph G is defined as a finite alternating

sequence of points and lines of the form v0, x1, v1, x2, v2, x2,v3, …,vn-1, x n, v n

beginning and ending with points such that each line xi is incident with
vi – 1 and vi.

Definition: The walk joins v0 and v n is called a v0 - v n walk. v0 is called the

initial point and v n is called the terminal point of the walk. The number of
lines in the walk is called the length of the walk.

Note:

1). No edge appears more than once in a walk.

2). A vertex may appear more than once.

3). The v0 - v n walk is also denoted by v0, v1, … ,v n.

4). A single point is considered as a walk of length 0.

CLOSED WALK AND OPEN WALK

Definition: A walk which begins and ends at the same point is called a closed
walk

i.e. a v0 – v n walk is called walk if v0 = v n .

A walk that is not closed is called an open walk.

62
CYCLE

Definition: A closed walk in which no point except the terminal point appear
more than once is called a cycle.

A closed walk v0, v1, v2, …,v n = v0 in which n ≥ 3 and v0, v1, v2, … ,v n-1
are distinct is called a cycle of length n.

The graph consisting of cycle of length n is denoted by C n.

C 3 is called a triangle.

TRIAL

Definition: A walk is called a trial if all its lines are distinct.

PATH

Definition: A walk is called a path if all its points are distinct.

Note:

1).Every path is a trial and a trail need not be a path.

2). The graph consisting of a trial with n points is denoted by Pn .

3).The length of a path in which the number of lines in the path.

Example: Consider the graph given in Fig. 3.1.

x5 v1 x1

v5 x6 v2

x4 x7 x2

v4 x3 v3 Fig. 3.1

1). v1, v2, v3, v4, v5 is a walk. It is a v1 – v5 walk.

63
 Initial point of the walk is v1. Terminal point of the walk is v5.

The length of the walk is 4.

2). v1, v2, v3, v4, v2,, v1, v2, v5, is a walk.

3). v1, v2, v4, v5, v2 and v1, v2, v3, v4, v5, v1 are closed walk.

4).v1, v2, v4, v3, v2, v5 is a trial but not a path.

5). v1, v2, v4, v5 is a path.

6). v2, v3, v4, v2 is a cycle.

Theorem 3.1: In a graph G, any u – v walk contains a u – v path.

Proof: We prove the result by induction on the length of the walk.

Any walk of length zero or one itself is a path.

Assume the result for all walks of length < n.

Prove the result for a walk of length n.

Let u = u0, u1, u2, …, un = v be a u – v walk of length n.

If all the points u0, u1, u2, …, un a are distinct then this walk itself is a
path.

If not, there exist i and j such that 0 ≤ i < j ≤ n and u i = u j .

Now u = u0, u1, u2, …, u i , u j + 1, …, un = v is a u – v walk of length < n.

 By induction hypothesis this walk contains u – v path.

Hence, any u – v walk contains a u – v path.

Theorem 3.2: If δ ≥ k then G is a path of length k..

64
Proof:

Let δ be the minimum degree of the graph G.

Let k be the number of vertices of the graph G.

Let P = {v0, v1, v2 , …, v n} be the longest path in G.

Then every vertex adjacent to v0 lies on P.

Since deg v0 ≥ δ, the length of P ≥ δ and δ ≥ k.

Hence P1 = { v0, v1, v2 , …, v k} is a path of length k in G.

Theorem 3.3: A closed walk of odd length contains a cycle.

Proof:

Let v0, v1, v2 , … , v n = v0 be a closed walk of odd length n .

Clearly n ≥ 3.

If n = 3 then the closed walk of length three is a triangle which is

trivially a cycle.

 The result is true for n = 3 .

Assume the result is true for all walks of length < n.

To prove the result for a closed walk v0, v1, v2 , … , v n = v0 of odd

length n .

If all the points in this walk are distinct then this walk itself is a cycle.

If not there exist two positive integers i and j such that i < j ,

{i , j} ≠ { 0 , n} and vi = v j , where n is odd.

65
Now vi, vi + 1, …, vj and v0, v1, v2 , … , vi, vj + 1 , … v n = v0 are closed
walks contained in the given walk and the sum of their lengths is n.

Since n is odd, at least one of these walks is of odd length.

Hence by induction hypothesis this closed walk contains a cycle.

 By the principle of Mathematical induction, the theorem is true for all

odd length n.

SOLVED PROBLEMS

Problem 1: If A is the adjacency matrix of a graph with V = {v1, v2 , …

, v p} then prove that for n ≥ 1 the (i , j)th entry of An is the number of

vi – v j walks of length n.

Solution:

Let G be a graph with vertex set V = {v1, v2 , … , v p}.

We know that ,

The adjacency matrix A = (a i j) p x p , where

a i j = 1 , if vi is adjacent to v j

0 , otherwise

We prove the result by induction on n.

When n = 1,

The number of vi – v j walks of length 1.

= 1 , if vi is adjacent to v j

0 , otherwise

66
 = (a i j) = (i , j )th element of A.

 The result is true for n = 1.

Assume that the result is true for n – 1.

Let An - 1 = (𝑎(𝑛−1)
𝑖𝑗
)

 (𝑛−1)
𝑖𝑗 = the number of vi – v j walks of length (n – 1).

Now An = An – 1. A

(𝑛−1)
= (𝑖𝑗 ) p x p (a i j)p x p

(i , j)th entry of An = ∑𝑝 (𝑛−1) ………..(1).

𝑖=1 𝑖𝑘 𝑎 𝑘𝑗

Take (𝑛−1)𝑎 = (𝑛−1) , if 𝑎 = 1 i.e. if v k is adjacent to v j

𝑖𝑘 𝑘𝑗 𝑖𝑗 𝑘𝑗

0 , if v k is not adjacent to v j

– 1
By induction hypothesis the (i , j)th entry of An is the number of
walks of length n - 1 between v i and v k if v k is adjacent to v j then the
above walk can be made into walks of length n between v i and v j.

(i , j)th entry of An is the number of walks of length n between v i

and v j.

Hence the theorem.

CONNECTEDNESS AND COMPONENTS

CONNECTEDNESS

Definition: Two points u and v of a graph G are said to be connected if

there exists a u – v path.

67
Definition: A graph G is said to be connected if there is at least one
path between every pair of vertices in G.

A graph G which is not connected is said to be disconnected.

COMPONENTS

Definition: Each of the connected graphs is called a component.

A graph G is connected iff it has exactly one component.

A graph G is disconnected then G has at least two components.

Example:
Connected Graphs

G1 G2 G3

Disconnected Graphs

G4 Fig. 3.2 G5

G1 is a connected graph with one component.

G2 is a connected graph with one component.

G3 is a connected graph with one component.

G4 is a disconnected graph with two components.

G5 is a disconnected graph with three components.

68
 𝑝−1
Theorem 3.4: A graph G with p points and δ ≥ is connected.
2

Proof:
𝑝−1
Let G be a graph and δ ≥ is connected.
2

To prove: G is connected.

Suppose G is not connected.

Then G has at least two components.

Consider G1 = (V1, X1) of G.

Let v1∊V1.
𝑝−1
We have δ ≥ .
2

∃ at least 𝑝−1
points in G1 which are adjacent to V1.
2

 V1 contains at least 𝑝−1 + 1 points.

2

𝑝+1
i.e. V1 contains .
2

Also G has at least two components.

The number of points in G ≥ 𝑝+1 +𝑝+1

2 2

i.e. p ≥ p + 1

Which is a contradiction to G has p points.

Hence G is connected.

Theorem 3.5: A graph G is connected iff for any partition of V into subsets V1
andV2 there is a line of G joining a points of V1 to a point of V2.

69
Proof:

Assume that G is connected.

Let V = V1U V2 and V1∩V2 = φ.

To prove: There is a line of G joining a point of V1 to a point of V2.

Let u ∊ V1 and v ∊ V2 .

Since G is connected, there exists a u - v path in G.

Let u = v0, v1, v2, …, vn = v be a path.

Let i be the least positive integer such that vi ∊ V2 .

Then v i - 1∊ V1.

The line v i – 1 v i joins a point of V1 to a point of V2.

Hence there is a line of G joining a point of V1 to a point of V2.

Conversely, assume that there is a line of G joining a point of V1 to a point of

V2.

To prove: G is connected.

Suppose G is not connected.

Then G contains at least two components say, G1 and G2.

Let V1 be the set of all points of G1 and V2 be the set of all points of V2.

Clearly V = V1 U V2 is a partition of V.

Also there is no line joining any point of V1 to a point of V2.

Which is a contradiction to the assumption.

 G is connected.

70
Theorem 3.6: If G is not connected then 𝐺̅ is connected.

Proof:

Suppose G is not connected.

Then G has at least two components.

Let u and v be any two points of G.

If u and v belong to different components of G then they are not adjacent in G.

 They are adjacent in 𝐺̅. Hence 𝐺̅ is connected.

If u and v lie in the same component of G then they are connected in G.

Choose w in the other component.

Then u, w, v is a u – v path in 𝐺̅.

Hence 𝐺̅ is connected.

DISTANCE

Definition: For any two points u, v of a graph we define the distance between

u and v by

d(u, v) = the length of a shortest u – v path if such a path exists

 , otherwise

Note:

If G is a connected graph then d(u, v) is always a non negative integer.

Hence, d is a metric on the set of points V.

71
Theorem 3.7: [Necessary and sufficient condition for a graph to be bipartite]

A graph G with at least two points is bipartite iff all its cycles are of even
length.

Proof:

Let G be a graph with at least two points is bipartite.

Then V can be partitioned into two subsets V1 and V2 such that every line joins
a point of V1 to a point of V2.

To prove: All its cycles are of even length.

Let v0, v1, v2, … , v n = v0 be a cycle of length n .

Choose v0 ∊ V1.

Then v2, v4, v6, … ∊ V1 and v1, v3, v5, … ∊ V2.

Also v n = v0 ∊ V1.

 n is even.

Hence all its cycles are of even length.

Conversely, assume that all cycles in g are of even length.

Without loss of generality we assume that G is connected.

To prove: G is bipartite.

Let v1 ∊ V1.

Define V1 = { v ∊ V/ d(v, v1) is even }

V2 = { v ∊ V/ d(v, v1) is odd }

Clearly, V = V1 U V2 and V1∩ V2 = φ.

72
Claim: Every line of G joins a point of V1 to a point of V2.

Suppose two points u, v ∊ V1 are adjacent.

Let P be the shortest v 1 – u path of length m and let Q be the shortest v 1 – v

path of length n.

Since u, v ∊ V1 , both m and n are even.

Let u1 be the last common point of P and Q.

Then the v 1 – u1 path along P and the v 1 – u1 path along Q are both shortest
path and hence have the same length, say i.

Now the u 1 – u path along P, the line u v followed by the v 1 – u1 path along Q
form a cycle.

Its length is = (m – i) + 1 +(n – i) = m + n – 2i +1 = odd number.

This is a contradiction to our assumption.

Hence no two points of V1 are adjacent.

Similarly, we can prove that no two points of V2 are adjacent.

Thus every line joins a point of V1 to a point of V2.

Hence G is bipartite.

CUT POINT

Definition: A cut point of a graph G is a point whose removal increases the

number of components.

BRIDGE

Definition: A bridge of a graph G is a line whose removal increases the number

of components.

73
Note: If v is a cut point of a connected graph then G – {v} is
disconnected.

Example:

3 7 6

1 2 4 5

Fig. 2.3 8

For the graph given in Fig. 2.3,

2, 4, 5 are cut points.

{2, 4} and {5, 8} are bridges.

Theorem 3.8: Let v be a point of a connected graph G. Then the following

statements are equivalent.

(i). v is a cut - point of G.

(ii).There exists a partition of V – {v} into subsets U and W such that

for each u ∊ U and w ∊ W, the point v is on every u – w path.

(iii).There exists two points u and w distinct from v such that v is on

every u – w path.

Proof: Let G be a connected graph and v be a point of G.

To prove: (i) ⇒ (ii) ⇒ (iii) ⇒ (i).

First, we prove: (i) ⇒ (ii).

Assume that v is a cut - point of G.

Then G – v is disconnected.

74
  G – v contains at least two components.

Let U be the set of points in one component and W be the set of

points in the remaining components.

 V – {v} = U 𝖴 W and U ∩ W = φ .

i.e. There exists a partition of V – {v} into subsets U and W.

To prove: each u ∊ U and w ∊ W, the point v is on every u – w path.

Let u ∊ U and w ∊ W.

Then u and w lie on different component of G – v.

 There is no u – w path in G – v.

Hence the point v lies on every u – w path in G.

Secondly, to prove: (ii) ⇒ (iii)

This is trivially true.

Thirdly, to prove: (iii) ⇒ (i)

Assume that there exists two points u and w distinct from v such that v

is on every u – w path.

 there is no u – w path in G – v.

⇒ G – v is disconnected.

Hence v is a cut - point of G.

Theorem 3.9: Let x be a line of a connected graph G. Then the following

statements are equivalent.

(i). v is a bridge of G.

75
 (ii).There exists a partition of V into subsets U and W such that for

every point u ∊ U and w ∊ W, the line x is on every u – w path.

(iii).There exists two points u and w such that the line x is on every

u – w path.

The Proof is similar to theorem 3.8 and is left as an exercise.

Theorem 3.10: A line x of a connected graph G is a bridge iff x is not

on any cycle of G.

Proof: Let G be a connected graph.

Let the line x be a bridge of G ................................................ (1).

Then G – x is disconnected.

To prove: x is not on any cycle C of G.

Suppose x is on any cycle C of G.

Let w1 and w2 be any two points in G.

Since G is connected, there exists a w1 – w2 path P in G.

If x is not on P, then P itself is a w1 – w2 path in G – x.

 G – x is connected , which is a contradiction to (1).

If x is on P, then replace x by C – x , we get a w1 – w2 walk in G – x.

This walk contains a w1 – w2 path in G – x.

 G – x is connected , which is a contradiction to (1).

Conversely, assume that x is not on any cycle of G ...................... (2)

To prove: x is a bridge of G.

76
Suppose x is not a bridge.

Then G – x is connected.

Let x = u v.

Then there exists a u - v path in G – x.

This path together with the line x = u v forms a cycle containing x .

This is a contradiction to (2). i.e. to x is not on any cycle of G.

Hence x is a bridge.

Theorem 3.11: Every non – trivial connected graphs has at least two points
which are not cut points.

Proof: Let G be a non – trivial connected graph.

Choose two points u and v such that d (u , v) is maximum.

To prove: u and v are not cut points.

Suppose v is a cut point.

Then G – v is disconnected.

 G – v has at least two components.

Choose a point w in a component that do not contain u.

Then v lies on every u – w path.

 d (u , w) > d (u , v).

This is a contradiction to d (u, v) is maximum.

v is not a cut point.

Similarly we can prove that u is not a cut point.

77
Hence G has at least two points which are not cut points.

BLOCKS

Definition: A connected non – trivial graph having no cut point is a block.

A block of a graph is a sub graph and which is connected.

Example: A graph and its blocks are given in Fig. 3.4.

G Blocks of G

Fig.3.4

Theorem 3.12: Let G be a connected graph with at least three points.

The following statements are equivalent.

(1). G is a block.

(2). Any two points of G lie on a common cycle.

(3). Any point and any line of G lie on a common cycle.

(4). Any two lines of G lie on a common cycle.

Proof: Let G be a connected graph with at least three points.

(i). To prove: (1) ⇒ (2).

Assume that G is a block..

Then G has no cut points.

To prove that any two points of G lie on a common cycle.

Let u and v be any two points in G.

78
We prove the result by using induction on d (u, v).

If d (u, v) = 1 then u and v are adjacent and G ≠ K2 , Since G has

at least three points.

Also G has no cut points.

 x = u v is not a bridge.

By theorem 2. 10, x lies on a common cycle.

Hence the points u and v lie on a common cycle of G.

Assume the result for any two points at distance less than k .

To prove the result for d (u , v ) = k , where k ≥ 2 .

Consider a u – v path of length k .

Let w be a point that precedes v on this path.

Then d (u , w ) = k – 1.

By induction hypothesis, the points u and w lie on a common cycle

C of G.

Since G is a block, w is not a cut point of G.

 G - w is connected.

Hence there exists a u – v path not containing w .

Let 𝑣′ be the last point common to P and C. [ See Fig . 2. 5].

Since u is common to P and C , such a 𝑣′ exists.

79
 Q

u 𝑣′ P

w v

Fig. 2. 5

Let Q denote the u – 𝑣′ path along the cycle not containing the point w.

Now, u – 𝑣′ path along Q, 𝑣′ - v path along P, the line v w and w – u

path along C form a cycle.

This cycle contains both u and v.

Hence by induction, any two points of G lie on a common cycle.

(ii). To prove : (2) ⇒ (1).

Assume that any two points of G lie on a common cycle.

To prove that G is a block.

Since G is a connected non – trivial graph it is enough to prove that

G has no cut point.

Suppose v is a cut point.

By theorem 4.8, there exists two points u and w distinct from v

such that v lies on every u – w path.

Also by assumption, u and w lie on a common cycle. This cycle

determines two u – w paths and at least one of these paths does not

contain v .

80
 This is a contradiction , since v lies on every u – w path.

 v is a cut point.

Hence G is a block.

 (1) ⇔ (2).

(iii). To prove : (2) ⇒ (3).

Assume that any two points of G lie on a common cycle of G.

To prove that any point and any line lie on a common cycle.

Let u be a point and v w be a line of G.

By assumption u and v lie on a common cycle C.

If w lies on C, then the point u and the line v w lie on a common

cycle.

If w is not on C, let 𝐶′ be a cycle containing u and w .

This cycle determines two w – u paths and at least one of them does

not contain v. Denote this path by P.

Let 𝑢′ be the first point common to P and C.

Now, the line v w , the w - 𝑢′ path along P , 𝑢′ - v path in C

containing u form a cycle. This cycle contains the point u and the

line v w .

(iv). To prove : (3) ⇒ (2) is trivial.

 (2) ⇔ (3).

81
(v). To prove : (3) ⇒ (4) is trivial.

Assume that any point and any line lie on a common cycle.

To prove that any two lines of G lie on a common cycle.

Let u u1 and v w be two lines.

By assumption, the point u and the line v w lie on a common cycle

C.

Also the point u1 and the line v w lie on the common cycle 𝐶′ .

Now the line u u1, u1 w path along 𝐶′ , the line v w and the v – w
path along C form a cycle.

This cycle contains the lines u u1 and v w.

Hence any two lines of G lie on a common cycle.

(vi). To prove : (4) ⇒ (3) is trivial.

 (3) ⇔ (4).

Hence, the statements (1) , (2) , (3) and (4) are equivalent for any

connected graph with at least three points.

CONNECTIVITY

Definition: The connectivity  =  (G) of a graph G is the minimum

number of points whose removal gives a disconnected or trivial graph.

The line connectivity  = (G) of a graph G is the

minimum number of lines whose removal gives a disconnected or trivial
graph.

82
Examples:

1). The connectivity of a disconnected graph is 0.

2). The line connectivity of a disconnected graph is also 0.

3). The connectivity of a connected graph with one cut point is 1.

4). The line connectivity of a connected graph with a bridge is 1.

5). For the complete graph K p ,  = p – 1 =  .

Theorem 3.13: For any graph G,  ≤  ≤ δ .

Proof:

First we prove that  ≤ δ.

If G has no lines then  = 0 , δ = 0.

Otherwise removal of all the lines incident with a vertex of

minimum degree gives a disconnected graph.

  ≤ δ ......................................(1).

Now to prove  ≤ .

Case (i): G is disconnected or trivial.

Then  = 0, δ = 0.

Case (ii): G is a connected graph with a bridge x = u v.

Then  = 1.

In this case G = K2 or one of the points incident with x is a cut

point.

83
   = 1.

Hence  =  = 1.

Case (iii):  ≥ 2.

Then there exist  lines whose removal gives a disconnected graph.

 the removal of  - 1 lines gives a connected graph G with a bridge

x = u v.

For each of these  - 1 lines, elect an incident point different from u or v.

The removal of these  - 1 points removes all the  - 1 lines.

Hence the resulting graph is disconnected with a bridge x = u v.

  ≤  - 1.

Thus the removal of u or v gives a disconnected or trivial graph.

 ≤ .

Hence  ≤  ≤ δ .

Note: The inequality  ≤  ≤ δ is often strict inequality. i.e.  <  < δ.

Fig. 3. 6

 = 2 ,  = 3 and δ = 4.

84
Definition: A graph G is said to be n – connected if  (G) ≥ n and

n – line connected if  (G) ≥ n .

Note:

1). A non trivial graph is 1 – connected iff it is connected.

2). A non trivial graph is 2 – connected iff it is a block having more

than one line. Hence K 2 is the only block which is not 2 – connected.

SOLVED PROBLEMS

𝑝𝑘
Problem 1: Prove that if G is a k – connected graph then q ≥ .
2

Solution: Let G be a ( p , q ) graph.

Since G is k – connected ,  ≥ k .

 k ≤ δ , [since  ≤  ≤ δ]
1
Now q = ∑𝑝 𝑑𝑒𝑔𝑣
2 𝑖=1 𝑖

≥ 1 𝑝 δ , [since deg vi ≥ δ ]
2

𝑝 𝑘2
≥ , [since δ ≥  ≥ k ]

Problem 2: Prove that there is no 3 – connected graph with 7 edges.

Solution: Suppose G is a 3 – connected graph with 7 edges.

Then p ≥ 5 and  > 3.

3𝑝 𝑝𝑘
We have q ≥ , [since if G is a k – connected graph then q ≥ ]
2 2

⇒ q ≥ (3x5 / 2)

85
 ⇒ q ≥ 7.5

⇒ q ≥ 8 , which is a contradiction since G has only 7 edges.

Hence there is no 3 – connected graph with 7 edges.

Problem 3: Find the connectivity of K m , n .

Solution:

Connectivity  = min { m , n}

 = min { m , n}

δ = min { m , n}

  =  = δ.

Unit IV

Eulerian graph and Hamiltonian graph

EULERIAN GRAPHS

Definition : A closed trial containing all points and lines is called

an Eulerian trial .

A graph having an Eulerian trial is called an Eulerian graph.

Example:

Fig. 4.1 Fig. 4.2

86
The graph given in Fig. 4.1 and Fig. 4.1 are an Eulerian graphs.

87
Theorem 4.1: If G is a graph in which the degree of every vertex is atleast
two then G contains a cycle.

Proof:

Construct a sequence v, v1, v2 , … of vertices as follows.

Choose a vertex v.

Let v1 be any vertex adjacent to v.

Let v2 be any vertex adjacent to v1 other than v.

At any stage, if vertex vi , i ≥ 2 is already chosen, then choose v i + 1

to be any vertex adjacent to vi other than v i -1 .

Since degree of each vertex is at least 2, the existence of v i + 1 is

always guaranteed.

Since G has only a finite number of vertices, at some stage we

have to choose a vertex which has been chosen before.

Let v k be the first such vertex and let v k = v i where i < k.

Then v i , v i + 1 , . . . , v k is a cycle.

v4

v v1

v3 v2 Fig. 4.3

Euler’s problem:

In what type of graph G is it possible to find a closed trial running

through every edge of 𝐺̅′ ?

88
Theorem 4.2: The following statements are equivalent for a connected
graph G.

(1). G is Eulerian.

(2). Every point of G has even degree.

(3). The set of edges of G can be partitioned into cycles.

Proof:

(i). To prove (1) ⇒ (2):

Let G be an Eulerian graph.

Let T be an Eulerian trial in G with origin (and terminus) u .

Each time a vertex v occurs in T in a place other than the origin

and terminus , two of the edges incident with v are accounted for.

Since an Eulerian trial contains every edges of G, d(v) is even

for every v ≠ u.

For u , one of the edges incident with u is accounted for by the

origin of T, another by the terminus of T and others are accounted

for in pairs.

Hence d (u) is also even.

(ii). To prove (2) ⇒ (3).

Since G is connected and non - trivial every vertex of G has

degree at least 2, G contains a cycle Z.

The removal of the lines of Z results in a spanning sub graph G1 in

89
 which again every vertex has even degree.

If G1 has no edges then all the lines of G form one cycle and

hence (3) holds.

Otherwise, G1 has a cycle Z1.

Removal of the lines of Z1 from G1 results in a spanning sub graph

G2 in which every vertex has even degree.

Continuing the above process, when a graph Gn with no edge is

obtained, we obtain a partition of the edges of G into n cycles.

(iii). To prove (3) ⇒ (1):

If the partition has only one cycle, then G is obviously Eulerian,

since it is connected.

Otherwise let Z1, Z2, . . . , Zn be the cycles forming a partition of the

lines of G.

Since G is connected there exists a cycle Z i ≠ Z1 having a common

point v1 with Z1.

Without loss of generality, let it be Z2.

The walk beginning at v1 and consisting of the cycles Z1 and Z2 in

succession is a closed trial containing the edges of these two cycles.

Continuing this process, we can construct a closed trial containing

all the edges of G. Hence, G is Eulerian.

90
Corollary 1: Let G be a connected graph with exactly 2n, n ≥ 1, odd
vertices. Then the edge set of G can be partitioned into n open trials.

Proof:

Let G be a connected graph with exactly 2n, n ≥ 1, odd vertices.

Let the odd vertices of G be labeled v1, v2 , …, v n , w1, w2, . . . , w n in

any order.

deg (v i) = odd number and deg (w i) = odd number.

Add n edges (v1, w1), (v2, w2), . . . , (v n, w n) to G.

The resulting graph 𝐺̅′ may be a multi graph.

No two of these n – edges are incident with the same vertex.

Also every vertex of 𝐺̅′ is of even degree.

 𝐺̅′ has an Eulerian Trial T.

If we remove the n edges that we added to G from T then the open

trial T will split into n open trials.

Hence the edge set of G can be partitioned into n – open trials.

Corollary 2: Let G be a connected graph with exactly two odd vertices.

Then G has an open trial containing all the vertices and edges of G.

Proof:

This is only a particular case of corollary 1.

Obviously the open trial mentioned in corollary 2 begins at one of

the odd vertices and end at the other.

91
Note: Corollary 2 answers the following question:

“ Which diagram can be drawn without lifting one‟s pen from the
paper not covering any line segment more than once ? ”.

TRACEABLE (OR) ARBITRARILY TRAVERSABLE

Definition: A graph G is said to be arbitrarily traversable or traceable

from a vertex v if the following procedure always give an Eulerian trial.

Start at v and traversing any incident edge . On arriving at a

vertex u, depart through any incident edge not yet covered and continue
until all the edges are covered.

If a graph is arbitrarily traversable from a vertex then it is

obviously Eulerian.

The following theorem due to Ore ( 1951) tells just when a given
graph is arbitrarily traversable from a chosen point.

Theorem 4.3: [ Ore’s theorem ]

An Eulerian graph G is arbitrarily traversable from a vertex v in G

iff every cycle in G contains v.

Fleury’s Algorithm :

Step – 1:

Choose an arbitrary vertex v0 and set walk W0 = v0 .

Step – 2:

Suppose that the trial W i = v0 e1 v2 e2 … e i vi has been chosen. Then

Choose an edge e i + 1 from X(G) - {e1 , e2 , …, e i} in such a way that

(i). e i + 1 is incident with vi .

92
 (ii).Unless there is no alternative, e i + 1 is not a bridge of G -{e1, e2,...,e i}.

Step – 3:

Stop when step – 2 can no longer be implemented.

Note: Fleury‟s algorithm construct a trial in G.

If G is Eulerian then any trial in G constructed by Fleury‟s

algorithm is an Euerian trial in G.

Question 1: For what value of n , K n is Eulerian ?

Answer: K n is Eulerian when n is odd .

Question 2: For what value of m and n, K m, n is Eulerian ?

Answer: K m, n is Eulerian when both m and n are even.

HAMILTONIAN GRAPHS

In 1959, Sir William Hamilton devised a mathematical game on the

graph of the dodecahedron (Fig. 2.10).

Definition: A spanning cycle in a graph is called a Hamiltonian cycle.

A graph having a Hamiltonian cycle is called a Hamiltonian graph.

Fig. 4.4

93
Definition: A block with two non adjacent vertices of degree 3 and all
other vertices of degree 2 is called a theta graph.

Example:

Fig. 4.5 Fig. 4.6

The graphs given in the Fig. 4.5 and Fig. 4.6 are theta graphs.

Note:

A theta graph is non – Hamiltonian and every non – Hamiltonian

2 – connected graph has a theta sub graph.

Theorem 4.4: Every Hamiltonian graph is 2 – connected.

Proof:

Let G be a Hamiltonian graph.

Then G has a Hamiltonian cycle Z.

For any vertex v of G, Z – v is connected.

 G – v is connected.

i.e. any vertex in G will not be a cut point.

Hence the minimum number of points whose removal gives a

disconnected or trivial graph will be ≥ 2. i.e.  ≥ 2.

Thus G is 2 – connected.

94
Theorem 4.5: If G is Hamiltonian then for every non – empty proper subset
S of V(G), 𝜔 ( G – S) ≤ │S│ where 𝜔 (H) denotes the number of components
in any graph H.

Proof:

Let G be a Hamiltonian graph.

Then G has a Hamiltonian cycle Z.

Let S be any non – empty proper subset of V(G).

Clearly 𝜔 (Z – S) ≤ │S│

Also Z – S is a spanning sub graph of G – S.

 𝜔 (G – S) ≤ 𝜔 (Z – S)

≤ │S│.

Hence 𝜔 (G – S) ≤ │S│.

Example:

K n is Hamiltonian for all n.

K m, n is Hamiltonian if m = n.

When m < n, K m, n is non Hamiltonian.

Note :

1) The above theorem is useful in showing that some graphs are non
Hamiltonian.
2) The converse of the above theorem is not true. For example,
the Peterson graph (Ref. Fig. 1.4) satisfies the conditions of the
theorem but is non Hamiltonian.

95
Theorem 4.6: [Dirac Theorem , 1952] (Sufficient condition for a graphG
to be Hamiltonian).

If G is a graph with p ≥ 3 vertices and δ ≥ p / 2 then G is Hamiltonian.

Proof:

Let G be a graph with p ≥ 3 vertices and δ ≥ p / 2 .

Suppose the theorem is false.

Let G be a maximal ( with respect to number of edges) non

Hamiltonian graph with p vertices..

Since p ≥ 3, G is not complete.

 There exists two non adjacent vertices in G.

Let u and v be the non adjacent vertices in G.

Then G + u v is Hamiltonian.

Since G is non Hamiltonian, each Hamiltonian cycle of G + u v

must contain the line u v.

 G has a spanning path v1, v2 , …, v p with origin u = v1 and terminus

v = v p.

Let S ={v i / u v i +1 ∊ E} and T ={v i / i < p , v i v ∊ E}, E is the edge set

of G.

Clearly vp ∉ S U T

 │ S U T │ < p ....................................................... (1)

To prove S ∩ T = φ

96
 Suppose S ∩ T ≠ φ. Then there exists at least one vertex vi ∊ S ∩ T.

uvi +1 ∊ E and vi v ∊ E

Then v1, v2 , …, v i , v p, v p - 1 , …, v i + 1, v1 is a Hamiltonian cycle in G.

v1 v2 . . . . vi v i+1 . . . . . . v p-1 v p

Fig. 4.6

This is a contradiction to G in non Hamiltonian.

S∩T = φ ⇒│S∩T│= 0.

Hence (1) becomes, │S│ + │T│ < p ............................ (2)

Also by the definition of S and T,

│S│ = d (u) and │T│ = d (v).

But, d (u) ≥ δ ≥ p / 2 and d (v) ≥ δ ≥ p / 2

 d (u) + d (v) ≥ p ⇒ │S│ + │T│≥ p.

This is a contradiction to equation (2).

Hence G is Hamiltonian.

Theorem 4.7: Let G be a graph with p points and let u and v be

nonadjacent points in G such that d(u) + d(v) ≥ p. Then G is
Hamiltonian iff G + u v is Hamiltonian.

Proof:

Let G be a graph with p points and let u and v be nonadjacent

points in G such that d(u) + d(v) ≥ p .......................... (1)

97
Assume that G is Hamiltonian.

To prove that G + u v is Hamiltonian.

Since G is Hamiltonian, G has a Hamiltonian cycle Z.

This cycle Z is a Hamiltonian cycle in G + u v .

 G + u v is Hamiltonian.

Conversely, assume that G + u v is Hamiltonian.

To prove that G is Hamiltonian.

Suppose G is non Hamiltonian.

Let S = {v I / u v i +1 ∊ E} and

T = {v I / i < p , v i v ∊ E}, where E is the edge set of G.

Let v1 , v2 , …, v p be a spanning path in G with origin u = v1 and

terminus v = v p.

Clearly v p is not an element of S U T.

│S U T│ < p......................................................... (2)

Also S ∩ T = φ and │S│ = d(u) ; │T│ = d(v)

 (2) ⇒ │S│+│T│ < p .

i.e. d(u) + d(v) < p.

This is a contradiction to (1).

 G is Hamiltonian.

98
CLOSURE OF A GRAPH

Definition: The closure of a graph G with p points is the graph obtained

from G by repeatedly joining pairs of non - adjacent vertices whose
degree sum is at least p until no such pair remains. The closure of G
is denoted by c(G).

Theorem 4.8: c (G) is well defined.

Proof:

Let G be a graph with p vertices.

Let G1 and G2 be two graphs obtained from G by repeatedly joining

pairs of non – adjacent vertices whose degree sum is p until no such
pairs remains.

Let x1, x2, …, x m and y1, y2, …, y n be the sequences of edges added to
G in obtaining G1 and G2 respectively.

To prove that {x1, x2, … , x m} = { y1, y2, …, y n }.

If possible, let x i + 1 = u v be the first edge in the sequence

{x1, x2, …, xm} that is not an edge of G2.

Let H = G + { x1, x2, …, x i} .

Since x i + 1 = u v is the next edge to be added to H in the process of

constructing G1, we have

d H( u ) + d H( v ) ≥ p .

Also, H is a sub graph of G2.

 𝑑′ ( u ) ≥ d H( u ) and 𝑑′ ( v ) ≥ d H( v ) ,

where 𝑑′ (u ) and 𝑑′ ( v ) denote degrees of u and v in G2.

99
 Hence 𝑑′ (u) + 𝑑′ (v ) ≥ d H( u ) + d H( v )

≥p.

 x i + 1 = u v is the next edge to be added to H to get G2.

Hence each x i is an edge of G2.

Similarly we can prove that each y i is an edge of G1.

 { x1, x2, …, x m} = { y1, y2, …, y n }.

i.e. G1 = G2.

Hence c (G) is well defined.

Theorem 4.9: A graph is Hamiltonian iff its closure is Hamiltonian.

Proof:

Let x1, x2, …, x n be the sequences of edges added to G to get the

closure of G.

Let G1, G2, . . . , G n = c (G) be the successive graphs obtained.

Applying the theorem 2.20 repeatedly, we get

G is Hamiltonian iff G1 is Hamiltonian

iff G2 is Hamiltonian
.
.
.

iff G n = c (G) is Hamiltonian.

Corollary: Let G be a graph with at least 3 points. If c (G) is

complete then G is Hamiltonian.

100
Theorem 4.10: [Chavatal theorem , 1972]

Let G be a graph with degree sequence (d1, d2, . . . , d p) where

d1 ≤ d2 ≤ . . . ≤ d p and p ≥ 3. Suppose that for every value of m < ,

2

d m > m or d p – m ≥ p – m.

𝑝
( i.e. there is no value of m < for which d m ≤ m or d p – m < p – m ).
2

Then G is Hamiltonian.

Proof:

Let G be a graph with degree sequence (d1, d2, . . . , d p) where

d1 ≤ d2 ≤ . . . ≤ d p and p ≥ 3.

Suppose that there is no value of m < , d m ≤ m or d p – m < p – m.

2

To prove G is Hamiltonian.

i.e. to prove c (G) is complete.

Suppose c (G) is not complete.

Then there exist at least two non – adjacent vertices.

Let u and v be two non – adjacent vertices in c (G) with 𝑑′ (u) ≤ 𝑑′ (v )

and 𝑑′ (u ) + 𝑑′ ( v ) is maximum, where 𝑑′ (u ) denote the degree of
vertex v in c (G) .

Let 𝑑′ (u ) = m .

Here, u and v are not adjacent.

 𝑑′ (u ) + 𝑑′ ( v ) < p .

101
  𝑑′ (v ) < p – m .

We have 𝑑′ (u ) ≤ 𝑑′ ( v ) < p – m .

i.e. m < p – m .

i.e. m < 𝑝
2

 There is a value of m less than 𝑝 .

2

Let S denote the set of vertices in V – {v} which are not adjacent to v

in c (G).

Let T denote the set of vertices in V – {u} which are not adjacent to u

in c (G).

Clearly, │S│= p – 1 - 𝑑′ ( v ) and │T│= p – 1 - 𝑑′ ( u )

i.e. │S│ ≥ p – 1 - (p – m) , [ Since 𝑑′ (v ) < p – m ]

i.e. │S│ ≥ m – 1

 │S│> m

i.e. c (G) has at least m points with degree ≤ m .

Also, each vertex in T U {u} has degree ≤ p – m .

 │T│= p – 1 – m and │T U {u}│ = p – m .

i.e. c (G) has at least p – m vertices of degree ≤ p – m .

Because G is a spanning sub graph of c (G), degree of each point in G

cannot exceed that in c (G).

Hence G satisfies the condition that there is a value of m < 𝑝 ,d m ≤m

2

102
 and d p – m < p – m.

This is a contradiction to the hypothesis..

 c (G) is complete.

Hence G is Hamiltonian.

Problem 1: Show that the Peterson graph is Hamiltonian.

Solution: Consider the Fig. 2. 14.

2 b e 5

c d

3 4

Fig. 4.7

Let us label the vertices as in Fig. 4.7.

We know that, “ A regular spanning sub graph of degree 1 is

called a one – factor ”.

If the Peterson has a Hamilton cycle C then G – E (C) must be a

regular spanning sub graph of degree 1.

Let us find all 1 – factors in G and show that they are from the
Hamiltonian cycle of G.

103
Case (1):

Consider the subset A = { 1 a, 2 b, 3 c, 4 d, 5 e} of the edge set of G.

Clearly A is a 1 – factor of G.

But G – A is the union of two disjoint cycles and hence is not a

Hamiltonian cycle of G.

Case (2):

If the 1 - factor contains 4- edges from A then the only line passing
through the remaining two points must also be included in the one –
factor .

So, again we get A.

Case (3):

If the 1 - factor contains just 3- edges from A then two choices can
be made.

Choice -1:

Let the 1 – factor contains the edges 1 a , 2 b and 3 c . Now, the sub
graph induced by the remaining 4 points is the path

d e

4 5

The unique 1 – factor in this path is {4 d , 5 e}.

Thus the 1 – factor of G considered becomes A.

104
Choice -2:

Let the 1 – factor contains the edges 1a , 2b and 4d . The remaining

4 points is the path

c e 5

The unique 1 – factor in this path is {3 c , 5 e}.

Thus the 1 – factor of G considered becomes A.

Case (4):

If a 1 - factor contains just 2- edges from A then again two choices

are possible.

Choice -1:

Let the 1 – factor contain the edges 1 a and 2 b. Now, the sub graph
induced by the remaining 6 points gives the path

c e

d 5

3 4

Here the d point has degree 1.

Any 1 – factor of this sub graph must contain the edge 4 d .

Thus case (3) is repeated.

105
Choice -2:

Let the 1 – factor contain the edges 1 a and 3 c. Now, the sub graph
induced by the remaining 6 points gives the path.

2 b e

d 5

Here, the point 2 has degree 1.

 Any 1 – factor of this sub graph must contain the edge 2 b .

Thus case (3) is repeated.

Case (5):

Let the 1 – factor contain just one edge of A, say 1a.

The induced sub graph by the remaining 8 points is

b e

2 c d 5

3 4

i.e. b e 2 5

c d 3 4

This contains two different paths c e b d and 2345 each of length 3.

Here, degree of c = 1 = degree of d

 The 1 – factor must contain the edges 2 3 and 4 5.

106
 Hence the 1 – factor is { 1 a, c e , b d, 23, 45}.

Now, G – B is

2 a 5

b e

c d

3 4

It is the union of two disjoint cycles and hence it is not a Hamiltonian.

Case (6):

Suppose there exist a 1 – factor that does not contain any edge from A.

It can contain at most 2 –edges from the cycle 123451 and at most 2 -

edges from the cycle a c e b d a.

Hence it can contain at most 4 – edges.

Hence there does not exist such a 1 – factor.

From the above six cases, G has no Hamiltonian cycle.

 G is non Hamiltonian.

Exercises:

1). Give an example of a Hamiltonian graph G that contains an induced

sub graph isomorphic to the graph in Fig . 2.11.

2). Give an example of a Hamiltonian graph G such that c (G) is not

Complete.
3). Find the closure of C 5 + x and K 4 – x .

107
 Unit V
TREES
Characterisation of trees- center of tree- planarity – definition and properties –
characterization of planar graphs- thickness, crossing and outer planarity.

The Concept of a tree was discovered by Cayley in the year 1857.

Definition:

A graph which contains no cycles is called an acyclic graph.

A connected acyclic graph is called a tree.

Note:

 Any graph without cycles is also called a forest.

 Components of a forest are trees.

Example:

Fig. 5.1

All trees with six vertices is given in Fig. 5.1

CHARACTERISATION OF TREES

Theorem 5.1: Let G be a (p, q) graph. The following statements are

equivalent.

1. G is a tree.
2. Every two points of G are joined by a unique path.
3. G is connected and p = q + 1.
4. G is a cyclic and p = q + 1.

108
Proof:

Let G be a (p, q) graph .

To prove : (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (1).(i). To prove : (1) ⇒ (2)
Assume that G is a tree.

 G is a connected acyclic graph.

To prove that any two points of G are connected by a unique path.

Let u and v be any two points of G.

Since G is connected there exists a u – v path in G.

Suppose there exists two distinct u – v paths.

P1 : u = v0 , v1 , . . . , v n = v and

P2 : u = w0 , w1 , . . . , w m = v .

Let i be the least positive integer such that 1 ≤ i < m and w i ∉ P1.

 w i – 1 ∊ P1 ∩ P2.

Let j be the least positive integer such that i < j ≤ m and w j ∊ P1.

Then the w i – 1 - w j path along P2 followed by the w j – w i -1 path

along P1 form a cycle. This is a contradiction to G is acyclic.

Hence every two points of G are joined by a unique path.

(ii). To prove: (2) ⇒ (3).

Assume that every two points of G are joined by a unique path.

To prove that G is connected and p = q + 1.

Clearly, G is connected.

109
 To prove: p = q + 1.

Let us prove the result by using induction on p.

When p = 1 or p = 2 ; q=0 or q = 1

 The result is true when p = 1 or p = 2

Assume the result for all graphs with less than p points.

To prove the result for a graph G with p points.

Let u and v be any two points of G.

Then by the assumption there exists a unique u - v path in G.

Consider any line x on the path. Then G - x is a disconnected

graph with exactly two components G1 and G2.

Let G1 be a (p1, q1) graph and G2 be a (p2, q2) graph.

Then p1 + p2 = p and q1 + q2 = q – 1.

Clearly, p1 and p2 < p.

 By the induction assumption, p1 = q1 + 1 and p2= q2 + 1.

Now, p = p1 + p2

= q1 + q2 + 2.

= q–1+2

= q + 1.

Hence G is connected and p = q + 1.

(iii). To prove: (3) ⇒ (4).

110
 Assume that G is connected and p = q + 1.

To prove that Gis acyclic and p = q + 1.

Suppose that G contains a cycle of length n.

There are n points and n lines on this cycle.

Fix a point u on the cycle. Consider any one of the remaining

p - n points not on the cycle, say v .

Since G is connected we can find a shortest u - v path in G.

Consider the line on this shortest path incident with v.

The p – n lines thus obtained are all distinct.

 q ≥ (p – n) + n

⇒ q ≥ p

This is a contradiction to p = q + 1.

Hence G is acyclic and p = q + 1.

(iii). To prove: (4) ⇒ (1).

Assume that G is acyclic and p = q + 1.

To prove that G is a tree.

It is enough to prove that G is connected.

Suppose G is not connected. Then G has more than one component.

Let G1 , G2 , . . . , G k , k ≥ 2 be the components of G.

Since G is acyclic, each of these components is a tree.

111
  p i = q i + 1 for i = 1 , 2, . . . , k , where G i is a (p i , q i) graph.

 ∑ 𝑘𝑖=1 𝑝𝑖 = ∑ 𝑘𝑖=1 𝑞𝑖 + 1 .

⇒ p = q + k ≥ q + 2 , since k ≥ 2.

This is a contradiction to p = q + 1.

 G is connected.

Hence G is a tree.

Corollary: Every non – trivial tree G has at least two vertices of degree 1.

Proof:

Since G is non – trivial, d(v) ≥ 1 for all points v.

Also G is a tree.

 p = q + 1,

Now, ∑ d (v) = 2 q = 2( p – 1) = 2 p – 2.

⇒ d (v) = 1 for at least two vertices.

Theorem 5.2: Every connected graph has a spanning tree.

Proof:

Let G be a connected graph.

Let T be a minimal connected spanning sub graph of G.

To prove that T is a tree .

By the definition of T , for any line x of T, T – x is disconnected.

 x is a bridge of T.

112
 We know that, “ A line x of a connected graph G is a bridge iff x is

not on any cycle of G”.

 x is not on any cycle of T.

 T is acyclic.

Further, T is connected.

 T is a tree .

Hence T is a spanning tree of G.

Corollary: Let G be a (p, q) connected graph . Then q ≥ p – 1.

Proof:

Let G be a (p, q) connected graph .

We know that, “ Every connected graph has a spanning tree”.

 G has a spanning tree T.

 T has p points and p – 1 lines.

Hence q ≥ p – 1.

Theorem 5.3: Let T be a spanning tree of a connected graph G.

Let x = u v be an edge of G not in T. Then T + x contains a unique

cycle .

Proof:

Let T be a spanning tree of a connected graph G.

Also x = u v be an edge of G not in T.

113
 We have T is acyclic.

 Every cycle in T + x must contain the edge x.

Hence there exists a one to one correspondence between the cycles in

T + x and u – v path in tree T.

We know that , In a tree there is a unique u – v path.

Hence there is a unique cycle in T + x.

CENTRE OF A TREE

Definition: Let v be a point in a connected graph G. The eccentricity e

(v) is defined by e (v) = max { d(u, v) / u ∊ V(G)}

The radius r(G) is defined by r(G ) = min{ e (v) / v∊ V(G)}.

v is called a central point if e (v) = r(G ) and the set of all

central points is called the centre of G.

Example: Consider the graph given in Fig. 5.2.

v4 v6

v5

v3

v2

v1

Fig. 5.2

The eccentricity

e (v 1) = 4 ; e (v 4) = 3

114
 e (v 2) = 3 ; e (v 5) = 3

e (v 3) = 2 ; e (v 6) = 4

The radius r(G ) = min{ e (v) / v∊ V(G)}.

=2

Centre of G = { v / e (v) = r(G ) }

= v 3.

Theorem 5.4: Every tree has a centre consisting of either one point or
two adjacent points.

Proof:

The result is obvious for the trees K1 and K2.

Let T be any tree with p ≥ 2 points.

Then T has at least two end points and the maximum distance

from a given point u to any other point v occurs only when v is an

end point.

Now delete all the end points from T.

The resulting graph 𝑇′ is also a tree and also the eccentricity of

each point in 𝑇′ is exactly one less than the eccentricity of that

vertex in T.

 T and 𝑇′ have the same centre.

The process of removing end points is repeated .

Finally we get a successive trees having the same centre as T.

115
 Hence we obtain a tree which is either K1 or K2.

 The centre of T consists of either one point or two adjacent

points

Exercises:

1. Draw all trees with 4 and 5 vertices.

2. Prove that if G is a forest with p points and k components then G
has p – k points.
3. Prove that the origin and terminus of a longest path in a tree have
degree 1.
4. Show that every tree with exactly 2 vertices of degree 1 is a path.

PLANAR GRAPH AND THEIR PROPERTIES

Definition:

A Graph is said to be embedded in a surface S if it is drawn on

the surface S such that no two edges intersect ( cross over).

A graph is called planar if it can be drawn on a plane without

intersecting edges.

A graph is called non – planar if it is not planar.

A graph that is drawn on a plane without intersecting edges is

called a plane graph.

Examples:

(1). K 4 is a plane graph.

116
 Fig. 5.2
(2). K 2 , 3 is a plane graph or planar graph.

Fig.5.3

(3). The graph given in Fig. 5.4 (a) is planar even though it is not

plane.

v4 v4

v5 v3 v5 v3

v1 v2 v1 v2

(a) Fig. 5.4 (b)

Theorem 5.5: K5 is non – planar.

Proof:

We know that K5 has 5 vertices and 5 C 2 = 10 edges.

Let the vertices be v1, v2, v3, v4, v5.

Out of these 10 edges , 5 edges form a cycle v1, v2, v3, v4, v5 , v1.

This cycle divides the plane into two regions namely the interior

region and the exterior region.

The remaining 5 edges should be drawn either in the interior or in

117
 the exterior.

Suppose the edges v5 v3 and v1 v3 can be drawn in the interior region

without cross over.

The edges v4 v1 and v4 v2 can be drawn in the exterior region without

cross over.

Now the edge v2 v5 remains which cannot be drawn without cross over.

Hence K 5 is non – planar.

Definition: Let G be a graph embedded on a plane . Then  - G

is the union of disjoint regions. Such regions are called faces of G.

Each plane graph has exactly one unbounded face and it is called the
exterior face. The interior faces are bounded by cycles.

Theorem 5.6: A graph can be embedded in the surface of a sphere iff it

can be embedded in a plane.

Proof:

Q P

S P1 


 Q1




Fig5.5

Let G be a graph embedded on a sphere. Place the sphere on

a plane . Let S be the point of contact of the sphere with the plane.

118
Draw a normal to the plane and the normal intersects the surface of the

sphere at N.

Assume that the sphere is placed in such a way that the point N is

different from the vertices of G.

For each point P on the surface of the sphere draw the line NP and
it meets the plane at P1.

The point P1 is called the stereographic projection of P on the plane.

In this way the vertices and edges of G can be projected on the

plane which gives an embedding of the graph G in the plane.

 A graph G can be embedded in the plane.

Conversely, Assume that the graph G can be embedded in the plane.

The reverse process obviously gives an embedding of the graph in

the surface of the sphere.

Theorem 5.7: [Euler’s Polyhedron Formula]

If G is a connected plane graph having V , E and F as the vertices ,

edges and faces respectively, then │V│-│E│+ │F│= 2.

Proof: Let G be a connected plane graph.

We prove the theorem by using induction on the number of edges

of G.

If │E│ = 0 then clearly G = K1 , [ since G is connected].

 │V│ = 1 and │F│= 1.

119
 Now, │V│-│E│+ │F│= 1 – 0 +1 = 2

 The result is true when │E│ = 0.

Assume the result for all connected plane graphs with < │E│
edges.

To prove the result for a graph G with │E│ edges.

If G is a tree then │E│ = │V│- 1, │ F│ = 1.

Now, L. H. S. = │V│-│E│+ │F│

= │E│+1 -│E│+ 1

=2

= R. H. S.

 The result is true for G is a tree.

If G is not a tree then G contains some cycles.

Let x be an edge contained in some cycle of G.

Then 𝐺̅′ = G – x is a connected plane graph.

Also, │𝑉′ │ = │V│, │𝐸1│ = │E│ - 1 < │E│ and │𝐹1│ = │F│ - 1.

By induction assumption, │𝑉′ │-│𝐸1│+ │𝐹1│= 2.

i.e. │V│ - │E│ + 1 + │F│ - 1 = 2 .

i.e. │V│ - │E│ +│F│ = 2.

 The result is true for G is not a tree.

Hence by the induction principle, the result is true for all connected

plane graphs.

120
Corollary 1: If G is a plane (p, q) graph with a r faces and k
components then p - q + r = k +1.

Proof:

Consider a plane embedding of G such that the exterior face of each

component contains all other components.

Let the i t h component be a (p i , q i ) graph with r i faces for each i.

Then each component is a connected plane graph.

 By Euler‟s Polyhedron formula,

p i - q i + r i = 2.

 ∑𝑘𝑖=1 𝑝𝑖 - ∑ 𝑘𝑖=1 𝑞𝑖 + ∑𝑘𝑖=1 𝑟𝑖 = ∑ 𝑘𝑖=1 2 ……….(1)

Also, ∑𝑘𝑖=1 𝑝𝑖 = p, ∑𝑘𝑖=1 𝑞𝑖 = q , ∑ 𝑘𝑖=1 𝑟𝑖 = r + (k – 1)

 p - q + r + (k – 1) = 2k

i.e. p - q + r = k + 1.

Corollary 2: If G is a (p, q) plane graph in which every face is an

𝑛(𝑝−2)
n cycle then q = .
𝑛−2

Proof:

Let G be a (p, q) plane graph in which every face is an n cycle .

 Each edge lies on the boundary of exactly two faces.

Let f 1, f 2, . . . , f r be the faces of G.

Then 2 q = ∑𝑖=1
𝑟 ( number of edges in the boundary of the face f i).

121
 = ∑ 𝑟𝑖=1 𝑛 , since each face is an n - cycle

=nr

2
⇒r= .
𝑛

By Euler‟s theorem,

p - q + r = 2.
2𝑞
i. e. p - q + = 2.
𝑛

2
⇒ q ( - 1) =2 - p
𝑛

(𝑝−2)
⇒ q = .
𝑛−2

Corollary 3: In any connected plane (p, q) graph , p ≥ 3 , with r faces

then q ≥ 3𝑟 and q ≤ 3 p - 6.
2

Proof:

Let G be any connected plane (p, q) graph with r faces and

p ≥ 3.

Case 1: Let G be a tree.

Then q = p - 1 and r = 1.

 p = q + 1 and r = 1.

p≥3⇒ q +1≥3

⇒q ≥ 2 >3
2

 q ≥ 3𝑟
2

122
 Also, p ≥ 3 ⇒ 2p ≥ 6

i.e. 2p + p ≥ 6 + p

⇒ 3p – 6 ≥ p > p – 1

i.e. 3p – 6 ≥ q

i.e. q ≤ 3p – 6.

Hence for a tree, 3𝑟 ≤ q ≤ 3p – 6.

2

Case 2: Let G have a cycle.

Let f 1, f 2, . . . , f r be the faces of G.

We know that, “ Each edge lies on the boundary of at most two faces”.

 2 q ≥ ∑𝑖=1
𝑟 ( number of edges in the boundary of the face f i).

≥ ∑ 𝑟𝑖=1 3 , [since each face is bounded by at least 3 edges]

= 3r

i.e. q ≥ 3𝑟.
2

By Euler‟s formula, p - q + r = 2

i.e. r = 2 + q – p.

We have q ≥ 3𝑟
2

3( 2+𝑞−𝑝)
q≥
2

i.e. 2q ≥ 6 + 3q – 3p .

i.e. 3p - 6 ≥ q

123
 ⇒ q ≤ 3p – 6.

Hence 3𝑟 ≤ q ≤ 3p – 6.
2

MAXIMAL PLANAR GRAPH

Definition: A graph is called a maximal planar if no line can be added

toit without losing planarity.

A graph is called a triangulated graph if each face is a triangle.

In a maximal planar graph, each face is a triangle.

Corollary 4: If G is a maximal planar (p, q) graph then and q = 3 p - 6.

Corollary 5: If G is a plane connected (p, q) graph without triangle

and p ≥ 3 then q ≤ 2p - 4.

Proof: Let G be a plane connected (p, q) graph without triangle and

p ≥ 3.

Case 1: Let G be a tree.

Then q = p – 1.

To prove q ≤ 2p - 4.

We have p ≥ 3 ⇒ p + p ≥ 3 + p

⇒ 2p ≥ 3 + q + 1

⇒ q ≤ 2p - 4.

Case 2: Let G have a cycle.

The boundary of each force has at least four edges. Also each
edge lies on at most 2 faces.

124
 2 q ≥ ∑𝑟𝑖=1 ( number of edges in the boundary of the face f i).

= ∑ 𝑟𝑖=1 4

= 4r

i.e. 2q ≥ 4r.

By Euler‟s formula, p - q + r = 2

i.e. r = 2 + q – p.

 2q ≥ 4(2 + q – p).

⇒ q ≤ 2p - 4.

Corollary 6: The graphs K5 and K 3, 3 are not planar.

Proof:

We know that,

“K5 is a connected (5, 10) graph”.

and “ In any connected plane ( p, q) graph p ≥ 3 , q ≤ 3 p - 6 ”.

Here, 3 p – 6 = 3 x 5 – 6 = 9

i.e. 10 ≰ 9

⇒ the inequality q ≤ 3 p - 6 is not satisfied.

Hence K 5 is not planar.

Next, To prove K 3, 3 is not planar.

We know that, K 3, 3 is a complete bipartite (6, 9) graph.

AlsoK 3, 3 has no triangles.

125
 We also know that “ If G is a plane connected ( p, q) graph without
triangle p ≥ 3 then q ≤ 2p - 4”.

Here 2p - 4 = 2 x 6 – 4 = 8

 9 ≰ 8 ⇒ q ≰ 2p - 4 .

Hence K 3, 3 is not planar.

Corollary 7: Every planar graph G with p ≥ 3 points has at least three

points of degree < 6.

Proof:

Let G be a planar graph with p ≥ 3 points.

To prove that G has at least three points of degree < 6.

By corollary 3, q ≤ 3 p - 6

 2 q ≤ 6 p - 12

i.e. ∑𝑝𝑖=1 𝑑𝑖 ≤ 6 p - 12 .................................. (1).

Suppose at most two points have degree < 6.

Also G is connected.

d i ≥ 1 , ∀ i.

𝑝
∑𝑖=1 𝑑𝑖 ≥ 6 + 6 + . . . + (p -2) + 1 +1

= 6 ( p – 2) + 2

= 6 p – 10

i.e. ∑𝑝𝑖=1 𝑑𝑖 ≥ 6 p – 10

This is a contradiction to (1).

126
 Hence G has at least three points of degree < 6.

Theorem 5.8: Every polyhedron has at least two faces with the
same number of edges on the boundary.

Proof:

Let G be the graph got from the polyhedron.

Then G is planar and 3 – connected.

i.e.  ≥ 3

δ ≥ 3 , [ Since  ≤  ≤ δ ]

We know that “ The number of faces adjacent to any given face f is

equal to the number of boundary edges of the face f ” .

Let f 1, f 2, . . . , f m be the faces of the polyhedron and e i be the

boundary edges of the face f i .

Let the faces be labeled in such a way that e i ≤ e i + 1 for every i .

To prove that there exists at least two faces with the same number of

boundary edges.

Suppose no two faces have the same number of boundary edges.

Then e i +1 - e i ≥ 1 for every i .

 ∑𝑚−1( e i +1 - e i) ≥ ∑𝑚−1 1 = m – 1.
𝑖=1 𝑖=1

𝑖=1( e i +1 - e i) = (e2 – e1) + (e3 – e2) + . . . +(e m - e m – 1)

Also, ∑𝑚−1

= e m - e1

i.e. e m - e1 ≥ m – 1.

127
 i. e. e m ≥ (m – 1) + e1

i.e. e m ≥ m + 2 , [ since e1 ≥ 3 ]

i.e. The m th face is adjacent to at least (m + 2) faces.

This is a contradiction to the fact that there are only m faces.

Hence there exists at least two faces with the same number of

boundary edges.

CHARACTERISATION OF PLANAR GRAPH

(1). A graph is planar iff all its blocks are planar.

(2). A disconnect graph is planar iff each of its components are planar.

(3). Every subgraph of a planar graph is planar.

Definition: Let x = u v be an edge of a graph G. The line x is

said to be subdivided when a new point w is adjoined to G and the
line x isreplaced by the lines u w and w v. This process is also called
an elementary subdivision of the edge x.

Two graphs are called homeomorphic if both can be obtained from

the same graph by a sequence of subdivisions of the lines.

Solved Problem:

Problem 1: If a (p1, q1) graph and a ( p2, q2) graph are homeomorphic
then p1 + q2 = p2 + q1.

Solution:

Assume that the graphs G1(p1, q1) and G2(p2, q2) are homeomorphic.

128
 Then G1 and G2 can be got from a (p, q) graph G by a series of
elementary subdivisions.

Let G1 can be got from G by r elementary subdivisions and G2 can

be got from G by s elementary subdivisions.

In each elementary subdivision , the number of points as well as the

number of lines increases by one.

 p1 = p + r , q1 = q + r ; p2 = p + s , q2 = q + s .

L. H. S. = p1 + q2 = p + r + q + s

= (p + s) + (q + r)

= p2 + q1

= R. H. S.

Theorem 5.9: [Kuratowski Theorem, 1930]

A graph is planar iff it has no subgraph homeomorphic to K5 or K 3, 3.

Note:

1). The above Kuratowski theorem gives the necessary and sufficient
condition for a graph to be planar.

2). The graphs K5 or K 3, 3 are called Kuratowski graphs.

THICKNESS, CROSSING AND OUTER PLANARITY

Definition: The crossing number of a graph G is the minimum number

of pair wise intersections of the edges when G is drawn in the plane.

The crossing number of a planar graph is zero.

The crossing number of each of the Kuratowski graphs is one.

129
Definition: A planar graph is called outer planar if it can be embedded

in the plane so that all its vertices lie on the same face. This face is

often chosen to be the exterior face.

Definition: The outer planar graph is called maximal outer planar if no

line can be added without losing outer planarity.

Every maximal outer planar graph is a triangularisation of a

polygon. But, every maximal plane graph is a triangularisation of the

sphere.

Definition: The genus of a graph G is defined to be the minimum

Number of handles to be attached to a sphere so that G can be drawn on

The resulting surface without intersecting lines.

Every planar graph has genus 0.

K5 , K6, K7, K 3, 3 and K 4, 4 each has genus 1.

130