Reg. No.

Question Paper Code : 71691

B.E. / B.Tech. DEGREE EXAMINATION, APRIL/MAY 2017
Seventh Semester
Computer Science and Engineering
CS6702 - GRAPH THEORY AND APPLICATIONS
(Regulation 2013)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (𝟏𝟎 × 𝟐 = 𝟐𝟎 marks)
1. Define Euler graph. Show that an Euler graph is connected except for any isolated
vertices the graph may have.
2. Can there be a path longer than a Hamiltonian path (if any) in a simple, connected,
undirected graph? Why?
3. Define planar graphs.
4. Identify two spanning trees for the following graph:
A 1 B 2 C
6 5
4
10 8
3
11
F7

E 9 D

5. Does the following graph have a maximal matching? Give reason.

1 a
b
2
c

3 d
e

6. Draw K8 and K9 and show that thickness of K8 is 2 while thickness of K9 is 3.

7. State the rule of sum, the first principle of counting.
8. Use Venn diagram to represent the following scenario :
 If S: a set, C1= condition 1 and C2 = condition 2 satisfied by some elements of S,
indicate on the diagram - S, N(C1), N(C2), N(C1, C2) and N(C1, C2).
9. Give explanation for the following :Generating function for the no. of ways to have n
cents in pennies and nickels = (1 + 𝑥 + 𝑥 2 + ⋯ )(1 + 𝑥 5 + 𝑥10 + ⋯ )
10. Solve the recurrence relation 𝑎𝑛+1 − 𝑎𝑛 = 3𝑛2 – 𝑛, 𝑛 ≥ 0, 𝑎0 = 3.

Part B – (5 × 𝟏𝟔 = 𝟖𝟎 marks)

11 (a) Define the following terms:

(i) Walk
(ii) Euler path
(iii) Hamiltonian path
(iv) Subgraph
(v) Circuit
(vi) Complete graph (6)
From the given graph draw the following :
(vii) Walk of length 6
(viii) Is this an Euler graph? Give reasons
(ix) Is there a Hamiltonian path for this graph? Give reasons
(x) Find atleast two complete subgraphs (10)

4
A B
1 3
5
2
7
C D E
6
8 10
9

Or

(b) (i) List any five properties of trees (6)

(ii) Define eccentricity of a vertex V in a tree T and give an example tree and its
eccentricity from the root. (10)

12. (a) (i) Define spanning tree and give an example.

(ii) A farm has six walled plots full of water. The graph representation of it is
given below. Use the concepts of spanning tree, cut sets appropriately to
determine the following:
(1) How many walls will have to be broken so that all the water can be
drained out?
 (2) If only one plot was full of water and this had to be drained into all
other plots, then how many walls need to be broken?
v1

v6
v2
v7

v10 v9
v8

v4
v5 v3

Or
(b) State the Euler’s formula relating the number of vertices, edges and faces of a planar
connected graph. Give two conditions for testing for planarity of a given graph. Give
a sample graph that is planar and another that is non-planar.

13. (a) Describe the steps to find adjacency matrix and incidence matrix for a directed graph
with a simple example.
Or

(b) Write a note on chromatic polynomials and their applications.

14. (a) In how many ways can the 26 letters of the alphabet be permuted so that the patterns
car, dog, pun or byte occures? Use the principle of inclusion and exclusion for this.
Or
(b) When n balls numbered 1, 2, 3 . . . 𝑛 are taken in succession from a container, a
rencontre occurs if mth ball withdrawn is numbered m, 1 <= 𝑚 <= 𝑛.
Find the probability of getting
(i) no rencontres
(ii) exactly one rencontre
(iii) Atleast one rencontre and
(iv) r rencontries 1 <= 𝑟 <= 𝑛 . Show intermediate steps.

15. (a) If 𝑎𝑛 is count of number of ways a sequence of 1s and 2s will sum to n, for 𝑛 >= 𝜃.
Eg. 𝑎3 = 3 (i) 1, 1, 1 ; (ii)1, 2, and (iii) 2, 1 sum up to 3.
Find and solve a sequence relation for 𝑎𝑛 .
Or
(b) What are Ferrers diagrams? Describe how they are used to (i) represent integer
partition (ii) Conjugate diagram or dual partitions (iii) self-conjugates (iv)
representing bisections of two partition.

All the Best – No substitute for hard work.

 Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).

ANSWER KEY
APRIL / MAY - 2017
CS6702 - GRAPH THEORY AND APPLICATIONS
(Regulation 2013)
Part A – (𝟏𝟎 × 𝟐 = 𝟐𝟎 marks)
1. Define Euler graph. Show that an Euler graph is connected except for any
isolated vertices the graph may have.

A graph which contains an Eulerian circuit is called an Euler (Eulerian) graph.

i.e., A circuit visits every edge exactly once which starts and ends on the same vertex.
Since isolated vertices are present in Euler graph and every vertices must be
even. i.e., every vertex is connected in an Euler graph. So an Euler graph is connected
except for any isolated vertices.
.

2. Can there be a path longer than a Hamiltonian path (if any) in a simple,
connected, undirected graph? Why?
No. There is no path longer than a Hamiltonian path.

Hamiltonian path in a simple, connected, undirected graph is the longest path

as it includes all the vertices.

3. Define planar graphs.

A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn
on the plane in such a way that its edges intersect only at their endpoints.
Graph G: v1 e1 v2
e3
e4 e2
e5
v3 6 v4
4. Identify two spanning trees for the following graph:
A 1 B 2 C
6 5
4
10 8
3
11
F7

E 9 D
 Two spanning trees:
A 1 B 2 C A 1 B 2 C
6 5

10 3
11

E D E 9 D

5. Does the following graph have a maximal matching? Give reason.

1 a
b
2
c

3 d
e
Yes, the graph has a maximal matching. Three maximal matching are given. By
maximum network flow concept 3 edges can be connected from source to destination.
1 a 1 a 1 a
b b b
2 2 2
c c c

3 d 3 d 3 d
e e e

1 a
b
S 2 T
c

3 d
e
6. Draw K8 and K9 and show that thickness of K8 is 2 while thickness of K9 is 3.
A B
K8 K9

H C

G D

F E
 The thickness of a graph G is the minimum number of planar graphs in which the edges
of G can be partitioned. That is, if there exists a collection of k planar graphs, all having the
same set of vertices, such that the union of these planar graphs is G, then the thickness of G is
at most k.
A planar graph (K1 – K4) has thickness 1. The Graphs (K5 – K8) of thickness 2 are
called bi-planar graphs. The complete graph K8 is a bi-planar graph. But K9 is not a bi-planar
graph. i.e., K9 is tri-planar graph. So the thickness of K9 is 3.

7. State the rule of sum, the first principle of counting.

Rule of sum.
If the first task can be performed in m ways, while a second task can be performed in
n ways, and the two tasks cannot be performed simultaneously, then performing either task
can be accomplished in any one of m + n ways.
Example : A college library has 40 books on C++ and 50 books on Java. A student at this
college can select 40+50=90 books to learn programming language.

Rule of Product (counting principle)

If a procedure can be broken into first and second stages, and if there are m possible
outcomes for the first stage and if, for each of these outcomes, there are n possible outcomes
for the second stage, then the total procedure can be carried out, in the designed order, in mn
ways.
Example: A drama club with six men and eight can select male and female role in 6 x 8 = 48
ways.

8. Use Venn diagram to represent the following scenario :

If S: a set, C1= condition 1 and C2 = condition 2 satisfied by some elements of S,
indicate on the diagram - S, N(C1), N(C2), N(C1C2) and N(C1 C2).

9. Give explanation for the following :Generating function for the no. of ways to have
n cents in pennies and nickels = (𝟏 + 𝒙 + 𝒙𝟐 + ⋯ )(𝟏 + 𝒙𝟓 + 𝒙𝟏𝟎 + ⋯ )

For pennies, the sequence ⟨1, 1, 1, …⟩ corresponds to the formal power series and the
generating function is
 For nickels, the sequence is ⟨1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, …⟩ corresponds to another
geometric series and the generating function is

For pennies and nickels,

Clearly, the generating function is

10. Solve the recurrence relation 𝒂𝒏+𝟏 − 𝒂𝒏 = 𝟑𝒏𝟐 – 𝒏, 𝒏 ≥ 𝟎, 𝒂𝟎 = 𝟑.

Let n=0, 𝑎1 − 𝑎0 = 0 ⟹ 𝑎1 = 𝑎0 ⟹ 𝑎1 = 3
i.e., 3𝑛2 – 𝑛 = 0 ⟹ 3𝑛 − 1 = 0 ⟹ 𝑛 = 1/3

Part B – (5 × 𝟏𝟔 = 𝟖𝟎 marks)
11 (a) Define the following terms:
(i) Walk
(ii) Euler path
(iii) Hamiltonian path
(iv) Subgraph
(v) Circuit
(vi) Complete graph (6)

(i) Walk: A walk is defined as a finite alternating sequence of vertices and edges,
beginning and ending with vertices.
v1 v1

g a g a
c c
b b
v2 v2
v3 v3
d e f e f
d
h h
v4 v5 v4 v5
Graph G: v1 a v2 b v3 c v3 d v4 e v2 f v5 is a Open walk.

(ii) Euler path: A path in a graph G is called Euler path if it includes every edges exactly
once. Since the path contains every edge exactly once, it is also called Euler trail
v1 e4 v2

e1
e2 e3 e5
e6
v3 e67 v4
6
v4 e1 v1 e2 v3 e3 v1 e4 v2 e5 v4 e6 v3 e7 v4 is an Euler path.
(iii) Hamiltonian path: Hamiltonian path is a path between two vertices of a graph that
visits each vertex exactly once.
v1 e4 v2

e1
e2 e3 e5
e6
v3 e67 v4
6
v1 e2 v3 e7 v4 e5 v2 is an Hamiltonian path.

(iv) Subgraph: A graph G' is said to be a subgraph of a graph G, if all the vertices and all
the edges of G' are in G, and each edge of G' has the same end vertices in G' as in G.

Graph G: v1 e1 v2 e2 v3 v1 e1 v2 e2 v3
Subgraph G' of G:

e3 e4 e5 e4
e6 e4 e4
v4 6 v5 v6 v5 v6

(v) Circuit: A closed walk in which no vertex (except initial and final vertex) appears
more than once is called a circuit. i.e., a circuit is a closed and nonintersecting walk allowing
repetitions of vertices but not edges.
v1 v1

g a g a
c c
b b
v2 v2
v3 v3
d e f d e f
h h
v4 v5 v4 v5
Graph G: v2 b v3 d v4 e v2 is a circuit.

(vi) Complete graph: A simple graph G is said to be complete if every vertex in G is

connected with every other vertex. i.e., if G contains exactly one edge between each pair of
distinct vertices.
The complete graphs Kn for n = 1, 2, 3, 4, 5 are show in the following Figure.
From the given graph draw the following:
4
A B
1 3
5
2
7
C D E
6
8 10
9

F
(vii) Walk of length 6: A 1 C 9 F 8 D 7 E 10 F 6 B
A B
1

7
C D E
6
8 10
9

F
(viii) Is this an Euler graph? Give reasons
No, this graph is not an Euler graph, since it does not contain Euler circuit.
An Euler graph must have all even degree vertices, but in this graph D and B are odd
degree vertices. So this graph is not an Euler graph.

(ix) Is there a Hamiltonian path for this graph? Give reasons

4
A B
1 5
7
C D E

F
Yes, there is a Hamiltonian path in this graph, D 7 E 5 B 4 A 1 C 9 F is a Hamiltonian path.
As this path includes all the vertices exactly once, it is a Hamiltonian path.
(x) Find atleast two complete subgraphs

A B
3
C
2
7
D E
9

F
The subgraphs K6, K5, K4 are not possible, The subgraphs K3, K2, K1 are possible

Or

11 (b) (i) List any five properties of trees (6)

1. There is one and only one path between every pair of vertices in a tree T.
2. In a graph G there is one and only one path between every pair of vertices, G is a
tree.
3. A tree with n vertices has n-1 edges.
4. Any connected graph with n vertices has n-1 edges is a tree.
5. A graph is a tree if and only if it is minimally connected.
6. A graph G with n vertices has n-1 edges and no circuits are connected.

11 (b) (ii) Define eccentricity of a vertex V in a tree T and give an example tree and
its eccentricity from the root. (10)

The eccentricity E(v) of a vertex v in a graph G is the distance from v to the vertex
farthest from v in G; that is,
𝐸(𝑣) = max 𝑑(𝑣, 𝑣𝑖 )
𝑣𝑖 ∈𝐺
A vertex with minimum eccentricity in graph G is called a center of G
Graph G: a

d c
b
Distance d(a, b) = 1, d(a, c) =2, d(c, b)=1, and so on.
Eccentricity E(a) =2, E(b) =1, E(c) =2, and E(d) =2.
Center of G = A vertex with minimum eccentricity in graph G = b.

E(root)=3 E(root)=2 E(root)=2 E(root)=1

12. (a) (i) Define spanning tree and give an example.

A spanning tree in a graph G is a minimal subgraph connecting all the vertices of G. If

G is a weighted graph, then the weight of a spanning tree T of G is defined as the sum of the
weights of all the branches in T.
Graph G: Spanning Tree T: ̅:Complement of Tree T
𝑻
v1 e4 v2 v1
v1 e4 v2 v2
e1
e2 e3 e5 e1 e2 e5
e3
e6 e6
v3 e67 v4 v3 e67
v3 v4 v4
6
6
Example: K4

12. (a) (ii) A farm has six walled plots full of water. The graph representation of it is
given below. Use the concepts of spanning tree, cut sets appropriately to determine the
following:
(1) How many walls will have to be broken so that all the water can be
drained out?
(2) If only one plot was full of water and this had to be drained into all
other plots, then how many walls need to be broken?
 v1

v6
v7 v2

v10 v9
v8
v5
v4
v3

(1) Here n = 10 and e = 15. We shall have to select a set of six (15-10+1=6) walls such
that the remaining 9 walls constitute a spanning tree. Breaking 6 walls will drain the
water out.
v1

v6
v7 v2

v10 v9
v8
v5
v4
v3

(2) If only one plot was full of water. if this had to be drained into all other plots, then we
need to be broken 5 walls.
v1

v6
v7 v2

v10 v9
v8
v5
v4
v3
Or

12 (b) State the Euler’s formula relating the number of vertices, edges and faces of a
planar connected graph. Give two conditions for testing for planarity of a given
graph. Give a sample graph that is planar and another that is non-planar.

Euler Theorem:
A connected planar graph with n vertices and e edges has e — n + 2 regions (faces).
COROLLARY
In any simple, connected planar graph with f regions, n vertices, and e edges (e > 2), the
following inequalities must hold:
3
 𝑒 ≥ 2𝑓
 𝑒 ≤ 3𝑛 — 6.

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

which can be drawn on a plan such that no two of its edges intersect.
A graph that cannot be drawn on a plan without crossover its edges is called non-
planar.
Non-planar Graph H:
Planar Graph G:
13. (a) Describe the steps to find adjacency matrix and incidence matrix for a directed
graph with a simple example.
Incidence Matrix
An undirected or directed graph G with n vertices and m edges can be represented as
an incidence matrix A. Arbitrarily number the edges 1, 2, . . . , m and the vertices 1, 2, . . . , n.
For edge i: (j, k), there is an entry aij = −1 and an entry aik = 1. All other elements are zero.

Note: Aij=1 if the vertex vi and edge ej are incident,

Aij=-1 if the vertex vi and edge ej (reverse edge) are incident, and
Aij=0 otherwise.

Digraph and its incidence matrix

Adjacency matrix
Let G be an n-vertex directed graph. Let A be the n×n adjacency matrix of the graph
G. Element aij = 1 if and only if the edge (i, j) ∈ G. All other elements are zero. A row of A
lists the nodes at the tip of the outgoing edges while a column of A lists the nodes at the tail
of the incoming edges.

Digraph and the adjacency matrix

For a simple graph with vertex set V, the adjacency matrix is a square | V | × | V |
matrix A such that its element Aij is one when there is an edge from vertex i to vertex j, and
zero when there is no edge.
Or
13 (b) Write a note on chromatic polynomials and their applications.

Chromatic polynomial.
A graph G of n vertices can be properly colored in many different ways using a
sufficiently large number of colors. This property of a graph is expressed elegantly by means
of polynomial. This polynomial is called the Chromatic polynomial of G.
The value of the Chromatic polynomial Pn(λ) of a graph with n vertices the number of
ways of properly coloring the graph , using λ or fewer colors.
Let ci be the different ways of properly coloring G using exactly i different colors.
Since i colors can be chosen out of λ colors in
λ
( ) different ways,
𝑖
λ
there are ci( ) different ways of properly coloring G using exactly i colors λ out of 2 colors.
𝑖
Since i can be any positive integer from 1 to n (it is not possible to use more than n
colors on n vertices), the chromatic polynomial is a sum of these terms; that is,

Each ci has to be evaluated individually for the given graph.

Example:

A graph with even one edge requires at least two colors for proper coloring, and therefore
𝑐1 = 0.
A graph with n vertices and using n different colors can be properly colored in n! ways; that
is, 𝑐𝑛 = 𝑛!.
As an illustration, let us find the chromatic polynomial of the graph given in Figure
 Since the graph in Figure has a triangle, it will require at least three different colors
for proper coloring. Therefore, c1 = c2 = 0 and c5 = 5!. Moreover, to evaluate c3, suppose that
we have three colors x, y, and z. These three colors can be assigned properly to vertices v 1,
v2, and v3 in 3! = 6 different ways. Having done that, we have no more choices left, because
vertex v5 must have the same color as v3, and v4 must have the same color as v2. Therefore,
c6 = 6

Similarly, with four colors, v1, v2, and v3 can be properly colored in 4 • 6 = 24
different ways. The fourth color can be assigned to v4 or v5, thus providing two choices. The
fifth vertex provides no additional choice. Therefore, c4 = 24•2 = 48.
Substituting these coefficients in P5(λ), we get, for the graph in Figure
𝑃5 (𝜆)𝑜𝑓 𝐺 = 𝜆(𝜆 − 1)(𝜆 − 2) + 2𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3)
𝑃5 (𝜆)𝑜𝑓 𝐺 = 𝜆(𝜆 − 1)(𝜆 − 2)(𝜆2 − 5𝜆 + 7)
Applications:
 A graph consisting of only isolated vertices is 1-chromatic.
 Every tree with two or more vertices is 2-chromatic.
 A graph with one or more vertices is at least 2-chromatic.
 A graph consisting of simply one circuit with n ≥ 3 vertices is 2-chromatic if n is
even and 3-chromatic if n is odd.
 A complete graph consisting of n vertices is n-chromatic.
 Every planar graph has a chromatic number of four or less.
 Every triangular planar graph has a chromatic number of four or less.
 The regions of every planar, regular graph of degree 3 can be colored properly
with four colors.

14. (a) In how many ways can the 26 letters of the alphabet be permuted so that the
patterns car, dog, pun or byte occures? Use the principle of inclusion and
exclusion for this.
Find out the permutations possible with 26 alphabets where CAR occurs always
Group CAR and consider it as a single alphabet. So total 24 alphabets
Total number of permutations possible with 26 alphabets where CAR occurs always = 24!
Similarly, Total number of permutations possible with 26 alphabets where DOG occurs always = 24!
Total number of permutations possible with 26 alphabets where PUN occurs always = 24!
Total number of permutations possible with 26 alphabets where BYTE occurs always = 23!
Total number of permutations possible with 26 alphabets where CAR and DOG occurs always = 22!
Total number of permutations possible with 26 alphabets where CAR and PUN occurs always = 22!
Total number of permutations possible with 26 alphabets where CAR and BYTE occurs always = 21!
Total number of permutations possible with 26 alphabets where DOG and PUN occurs always = 22!
Total number of permutations possible with 26 alphabets where DOG and BYTE occurs always = 21!
Total number of permutations possible with 26 alphabets where PUN and BYTE occurs always = 21!

Total number of permutations possible with 26 alphabets where CAR,DOG and PUN occurs always = 20!
Total number of permutations possible with 26 alphabets where CAR,DOG and BYTE occurs always = 19!
Total number of permutations possible with 26 alphabets where CAR,PUN and BYTE occurs always = 19!
Total number of permutations possible with 26 alphabets where DOG, PUN and BYTE occurs always = 19!

Total number of permutations possible with 26 alphabets where CAR,DOG, PUN and BYTE occurs always=17!

Required number of permutations

= 26! - (24!+24!+24!+23!) + (22!+22!+22!+21!+21!+21!) - (20!+19!+19!+19!) - 17!

= 26! - [3*24! + 23!] + 3[22! + 21!] - [20! + 3*19!] - 17!

Or
14(b) When n balls numbered 𝟏, 𝟐, 𝟑 . . . 𝒏 are taken in succession from a container, a
rencontre occurs if mth ball withdrawn is numbered m, 𝟏 <= 𝑚 <= 𝑛.
Find the probability of getting
(i) no rencontres
(ii) exactly one rencontre
(iii) Atleast one rencontre and
(iv) r rencontries 𝟏 <= 𝑟 <= 𝑛 . Show intermediate steps.

Solution:
Rencontres means correct arrangement of 1 is in 1st , 2 is in 2nd place, and n is in nth place.
Derangements means 1 is not in first place, 2 is not in second place, and n is not in nth place.

We have n balls numbered 𝟏, 𝟐, 𝟑 . . . 𝒏.

1st place we have n choices,
2nd place we have n-1 choices,
…
nth place we have 1 choice.
All possible ways = n x (n-1) x (n-2) x … x 3 x 2 x 1 = n!
So, we can arrange n balls randomly in n! ways.
i.e., total possible arrangements = n!

(i) No rencontres (i.e., total derangements)

First, We need to find the probability of getting no rencontres.

Here, we arrange these n balls so that none of them is in its actual position.
i.e., we can arrange the numbers l, 2,3,..., n so that 1 is not in first place, 2 is not in second
place, and n is not in nth place.
These arrangements are called the derangements of l, 2,3,..., n and is denoted by dn = n!e-l
Thus, derangement of n balls is dn.
Hence, probability of getting no rencontres = (total derangements /total arrangements)
= dn/n!
= n!e-l /n!
= e-l

(ii) Exactly one rencontre

The correct way to place n balls numbered 𝟏, 𝟐, 𝟑 . . . 𝒏.

i.e., ball 1 in first place or ball 2 in second place, upto the ball n in nth place.
i.e., one ball out of n can be placed in correct position, this can be done in n ways.
Remaining (n-1) balls can be arranged in derangements, i.e., dn-1.

Probability of exactly one rencontre = n x (dn-1) / n!

= n x (n-1)! e-l / n!
= n! e-l / n!
= e-l
(iii) Atleast one rencontre
Probability of at least one rencontre = 1- Probability of total derangements
= 1- (dn/n!)
= 1- (n!e-l /n!)
= 1- e-l
(iv)r rencontries 𝟏 <= 𝑟 <= 𝑛 .
𝑛
Probability of r rencontries (1 <= 𝑟 <= 𝑛)=[( ) 𝑑𝑛−𝑟 ] /𝑛!
𝑟
≈ [n!/r! (n-r)!][(n-r)! e-l] / n! =
= (1/r!) e-l
15. (a) If 𝒂𝒏 is count of number of ways a sequence of 1s and 2s will sum to n, for 𝒏 > 0.
Eg. 𝒂𝟑 = 𝟑 (i) 1, 1, 1 ; (ii)1, 2, and (iii) 2, 1 sum up to 3.
Find and solve a sequence relation for 𝒂𝒏 .

Partitioning a positive integer n into positive summands and the number of such partitions without
regard to order is called partitions of integer. This number is denoted by P(n). An represents count of
such partitions. i.e., 3 = 1 + 1 +1 = 2 + 1 = 1+ 2, so a3 = 3.

Partitioning with 1 and 2

P(1) =1 a1 = 1
P(2) =2=1+1 a2 = 2
P(3) = 1 + 1 +1 = 2 + 1 = 1+ 2 a3 = 3
P(4) =1+1+1+1
=1+1+2=1+2+1=2+1+1
=2+2 a4 = 5
P(5) = 1 + 1+ 1 + 1 + 1
= 1+ 1 + 1 + 2 = 1+ 1 + 2 + 1 = 1+ 2 + 1 + 1 = 2 + 1 + 1 +1
= 1+ 2 + 2 = 2 + 1 + 2= 2 + 2 + 1 a5 = 8.
P(6) = (1, 1, 1, 1, 1, 1) => 6!/6! =1
= (1, 1, 1, 1, 2) => 5!/4!1! =5
= (1, 1, 2, 2) => 4!/2!2! =6
= (2, 2, 2) => 3!/3! =1 a6 = 1 + 5 + 6 + 1 = 13
P(7) = (1, 1, 1, 1, 1, 1, 1) => 7!/7! =1
= (1, 1, 1, 1, 1, 2) => 6!/5!1! =6
= (1, 1, 1, 2, 2) => 5!/3!2! = 10
= (1, 2, 2, 2) => 4!/3!1! = 4 a6 = 1 + 6 + 10 + 4 = 21
⸫ ai = {1, 2, 3, 5, 8, 13, 21, …} => This is a sequence of Fibonacci numbers.
i.e, an = an-1 + an-2 is the recurrence relation.

Consider the recurrence relation fn = fn-1 + fn-2 with initial conditions f0 = 0 and f1 = 1.
The characteristic equation is s2 − s − 1 = 0.

Or
15 (b) What are Ferrers diagrams? Describe how they are used to (i) represent integer
partition (ii) Conjugate diagram or dual partitions (iii) self-conjugates (iv) representing
bisections of two partition.
A Ferrers diagram represents partitions as patterns of dots, with the ith row having the same
number of dots as the ith term in the partition. The spelling "Ferrars" is sometimes also
used, and the diagram is sometimes called a graphical representation or Ferrers graph. A
Ferrers diagram of the partition
Ferrers graph uses rows of dots to represent a partition of an integer where the number of dots
per row does not increase as we go from any row to the one below it.
In Figure we find the Ferrets graphs for two partitions of 14: (a) 4 + 3 + 3 + 2 + 1 + 1 and (b)
6 + 4 + 3 + 1. The graph in part (b) is said to be the transposition of the graph in part (a), and
vice versa, because one graph can be obtained from the other by interchanging rows and
columns.
These graphs often suggest results about partitions. Here we see a partition of 14 into
summands, where 4 is the largest summand, and a second partition of 14 into exactly four
summands. There is a one-to-one correspondence between a Ferrers graph and its
transposition, so this example demonstrates a particular instance of the general result: The
number of partitions of an integer it into m summands is equal to the number of partitions of
n into summands where m is the largest summand.

(i) Representation of integer partition

Partitioning a positive n into positive summands and seeking the number of such partitions
without regard to order is called Partitions of integer. This number is denoted by p(n).
For example
P(1) = 1: 1
P(2) = 2: 2=1+1
P(3) = 3: 3 = 2 +1 = 1 + 1 +1
P(4) = 5: 4=3+1=2+2=2+1+1=1+1+1+1
P(5) = 7: 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1+ 1 = 1 + 1 + 1 + 1 + 1

Example
Find the generating function for pd(n), the number of partitions of a positive integer n into
distinct summands.
Partitions of 6 are:
1) 6
2) 5 +1
3) 4+2
4) 4+1+1
5) 3+3
6) 3+2+1
7) 3 + 1 + 1 +1
8) 2 +2+2
9) 2+2+1+1
10) 2+1+1+1+1
11) 1+1+1+1+1+1
Partitions (1), (2), (3), and (6) have distinct summands. So pd(6)=4

(ii) Conjugates diagram or dual partitions

Pairs of partitions for a single number whose Ferrers diagrams transform into each other
when reflected about the line y=-x, with the coordinates of the upper left dot taken as (0, 0),
are called conjugate (or transpose) partitions. For example, the conjugate partitions illustrated
above correspond to the partitions 6+3+3+2+1 and 5+4+3+1+1+1 of 15. A partition that is
conjugate to itself is said to be a self-conjugate partition.

(iii) self-conjugates

A partition whose conjugate partition is equivalent to itself. The Ferrers diagrams

corresponding to the self-conjugate partitions for 3<=n<=10 are illustrated above. The
numbers of self-conjugate partitions of n=1, 2, ... are 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5,
5, 5, 6, 7, ...

By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 + 1 + 1 of the number
14. Such partitions are said to be conjugate of one another.[16] In the case of the number 4,
partitions 4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1 are
conjugate of each other. Of particular interest is the partition 2 + 2, which has itself as
conjugate. Such a partition is said to be self-conjugate.
(iv) representing bisections of two partition.
Claim: The number of self-conjugate partitions is the same as the number of partitions with
distinct odd parts.
Proof (outline): The crucial observation is that every odd part can be "folded" in the middle to
form a self-conjugate diagram:
↔

One can then obtain a bijection between the set of partitions with distinct odd parts and the
set of self-conjugate partitions, as illustrated by the following example:

9+7+3 = 5+5+4+3+2
Dist. odd self-conjugate
Odd parts and distinct parts
Among the 22 partitions of the number 8, there are 6 that contain only odd parts:
7+1
5+3
5+1+1+1
3+3+1+1
3+1+1+1+1+1
1+1+1+1+1+1+1+1
Alternatively, we could count partitions in which no number occurs more than once. If we
count the partitions of 8 with distinct parts, we also obtain 6:
8
7+1
6+2
5+3
5+2+1
4+3+1
For all positive numbers the number of partitions with odd parts equals the number of
partitions with distinct parts. For every type of restricted partition there is a corresponding
function for the number of partitions satisfying the given restriction. An important example
is q(n), the number of partitions of n into distinct parts. The first few values of q(n) are
(starting with q(0)=1): 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, …

All the Best – No substitute for hard work.

Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).
 Reg. No. :

Question Paper Code : 80305

B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2016
Seventh Semester
Computer Science and Engineering
CS6702 - GRAPH THEORY AND APPLICATIONS
(Regulation 2013)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (𝟏𝟎 × 𝟐 = 𝟐𝟎 marks)

11. Define walk, path and circuit in a graph.

12. What is meant by eccentricity?
13. Define 1-isomarphic and 2- isomorphic.
14. What are the applications of planar graph?
15. Define minimal dominating set and maximal independent set.
16. Find the Chromatic number of a complete graph of n vertices.
17. In how many different ways can the letters of the word ‘LEADING’ be arranged in such
a way that the vowels always come together?
18. A committee including 3 boys and 4 girls is to be formed from a group of 10 boys and
12 girls. How many different committees can be formed from the group?
19. Define recurrence relation.
20. Define generating function.

Part B – (5 × 𝟏𝟔 = 𝟖𝟎 marks)

11 (a) (i) Show that the maximum number of edges in a simple graph with n vertices is
n(n-1)/2. (6)
(ii) Prove that if a graph has exactly two vertices of odd degree, there must be path
joining these two vertices. (5)
(iii) Prove that any two simple connected graphs with n vertices, all of degree two,
are isomorphic. (5)
Or
(b) (i) Mention some of the properties of tree. (5)
(ii) Prove that in any tree, there are atleast two pendant vertices. (5)
(iii) Show that a Hamiltonian path is a spanning tree. (6)

12 (a) (i) Explain max-flow min-cut theorem. (10)

(ii) Explain about Fundamental cut set and Fundamental circuit in a graph. (6)
Or
 (b) (i) Prove that every connected graph has atleast one spanning tree. (6)
(ii) Prove the graphs K5 and K3,3 are non planar. (10)

13 (a) (i) Prove- that every tree with two or more vertices is 2-chromatic. (5)
(ii) Prove that a graph of n vertices is a complete graph iff its chromatic
polynomial is Pn(λ) = λ (λ – 1) (λ – 2) … (λ - n + 1) . (6)
(iii) Prove that a covering g of a graph is minimal iff g contains no paths of length
three or more. (5)
Or
(b) (i) Explain Euler digraph. (10)
(ii) Discuss about some types of digraph with suitable example. (6)

14 (a) (i) How many arrangements are there of all the vowels adjacent in
SOCIOLOGICAL? (4)
(ii) Find the value of n for the following: 2P(n, 2) + 50 = P(2n,2) (5)
(iii) How many distinct four-digit integers can one make from the digits 1, 3, 3, 7,
7 and 8? (4)
(iv) In how many possible ways could a student answer a 10-question true-false
test? (3)
Or
(i) How many arrangements of the letters in MISSISSIPPI has no consecutive
S's? (4)
(ii) A gym coach must select 11 seniors to play on a football team. If he can make
his selection in 12,376 ways, how many seniors are eligible to play? (4)
(iii) How many permutations of size 3 can one produce with letters m, r a, f and t?
(4)
(iv) Rama has two dozen each of n different colored beads. If she can select 20
beads (with repetitions of colors allowed), in 230,230 ways, what is he value
of n? (4)

15 (a) (i) Discuss about exponential generating function with an example. (10)
(ii) Find the unique solution of the recurrence relation. 6an-7an-1=0, n≥1, a3=343.
(6)
Or
(b) (i) The population of Mumbai city is 6,000,000 at the end of the year 2015. The
number of immigrants is 20000n at the end of year n. the population of the city
increases at the rate of 5% per year. Use a recurrence relation to determine the
population of the city at the end of 2025. (8)
(ii) Write short note on Summation operator. (8)

All the Best – No substitute for hard work.

Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).
 ANSWER KEY
B.E. / B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2016
Seventh Semester
Computer Science and Engineering
CS6702 - GRAPH THEORY AND APPLICATIONS
(Regulation 2013)
Time : Three hours Maximum : 100 marks
Answer ALL Questions
Part A – (𝟏𝟎 × 𝟐 = 𝟐𝟎 marks)

1. Define walk, path and circuit in a graph.

A walk is defined as a finite alternating sequence of vertices and edges, beginning and
ending with vertices. No edge appears more than once. It is also called as an edge train or a
chain.
An open walk in which no vertex appears more than once is called path. The number
of edges in the path is called length of a path.
A closed walk in which no vertex (except initial and final vertex) appears more than
once is called a circuit. That is, a circuit is a closed, nonintersecting walk.
v1 v1 v1

g a g a c g a
c c
b b b
v2 v2 v2
v3 v3 v3
e f e f d e f
d d
h h h
v4 v5 v4 v5 v4 v5

Graph G: Open walk Path of length 3

v1 a v2 b v3 c v3 d v4 e v2 f v5 is a walk. v1 and v5 are terminals of walk.

v1 a v2 b v3 d v4 is a path. a v2 b v3 c v3 d v4 e v2 f v5 is not a path.
v2 b v3 d v4 e v2 is a circuit.

2. What is meant by eccentricity?

The eccentricity E(v) of a vertex v in a graph G is the distance from v to the vertex
farthest from v in G; that is,
𝐸(𝑣) = max 𝑑(𝑣, 𝑣𝑖 )
𝑣𝑖 ∈𝐺
Graph G: a

c e
d
b
Distance d(a, b) = 1, d(a, c) =2, d(c, b)=1, d(a, d) =3 and so on.
Eccentricity E(a) =3, E(b) =2, E(c) =2, E(d) =3, and E(e) =3.
3. Define 1-isomarphic and 2- isomorphic.
1-Isomorphism
A graph G1 was 1-Isomorphic to graph G2 if the blocks of G1 were isomorphic to the
blocks of G2.
Two graphs G1 and G2 are said to be 1-Isomorphic if they become isomorphic to each
other under repeated application of the following operation.
Operation 1: “Split” a cut-vertex into two vertices to produce two disjoint subgraphs.

Graph G1: Graph G2:

Graph G1 is 1-Isomorphism with Graph G2.

2-Isomorphism
Two graphs G1 and G2 are said to be 2-Isomorphic if they become isomorphic after
undergoing operation 1 or operation 2, or both operations any number of times.
Operation 1: “Split” a cut-vertex into two vertices to produce two disjoint subgraphs.
Operation 2: “Split” the vertex x into x1 and x2 and the vertex y into y1 and y2 such
that G is split into g1 and g2. Let vertices x1 and y1 go with g1 and
vertices x2 and y2 go with g2. Now rejoin the graphs g1 and g2 by merging
x1 with y2 and x2 with y1.

4. What are the applications of planar graph?

i. Planar graph – A graph that can be embedded in the plane, i.e., it can be drawn
on the plane in such a way that its edges intersect only at their endpoints.
ii. To eliminate the distinction between finite and infinite regions, a planar graph is
often embedded in the surface of sphere. This is done by stereographic
projection.
iii. Euler's formula states that if a finite, connected, planar graph is drawn in the
plane without any edge intersections, and v is the number of vertices, e is the
number of edges and f is the number of faces (regions bounded by edges,
including the outer, infinitely large region), then 𝑣 − 𝑒 + 𝑓 = 2.
iv. In any planar graph, drawn with no intersections, the edges divide the planes into
different regions (windows, faces, or meshes). The regions enclosed by the
planar graph are called interior faces of the graph. The region surrounding the
planar graph is called the exterior (or infinite or unbounded) face of the graph.
5. Define minimal dominating set and maximal independent set.
A dominating set (or an externally stable set) in a graph G is a set of vertices that
dominates every vertex v in G in the following sense: Either v is included in the dominating
set or is adjacent to one or more vertices included in the dominating set.
c
f
a b e

d g

{b, g} is a dominating set, {a, b, c, d, f} is a dominating set. Set of all vertices is a

dominating set.
A minimal dominating set is a dominating set from which no vertex can be removed
without destroying its dominance property. {b, e} is a minimal dominating set.
A set of vertices in a graph is said to be an independent set of vertices or simply
independent set (or an internally stable set) if two vertices in the set are adjacent.
A maximal independent set is an independent set to which no other vertex can be
added without destroying its independence property. {a, c, d, f} is one of the maximal
independent set. {b, f} is one of the maximal independent set.

6. Find the Chromatic number of a complete graph of n vertices.

The chromatic polynomial of a complete graph of n vertices is calculated by

𝑃𝑛 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2) … (𝜆 − 𝑛 + 1) with λ colors

Example: 𝑃4 (𝜆) = 𝜆(𝜆 − 1)(𝜆 − 2)(𝜆 − 3) for a complete graph K4.

7. In how many different ways can the letters of the word ‘LEADING’ be arranged
in such a way that the vowels always come together?
The number of different ways of arrangement of the word “LEADING”= 7!=5040.

8. A committee including 3 boys and 4 girls is to be formed from a group of 10 boys

and 12 girls. How many different committees can be formed from the group?
10! 12! 10.9.8 12.11.10.9
The number of possible different committees =10C3* 12C4=3!7!*4!8!= *
3.2.1 4.3.2.1
=120*495=59400.

9. Define recurrence relation.

A recurrence relation is an equation that recursively defines a sequence or
multidimensional array of values, once one or more initial terms are given: each further term
of the sequence or array is defined as a function of the preceding terms.
The term difference equation sometimes (and for the purposes of this article) refers to a
specific type of recurrence relation. However, "difference equation" is frequently used to
refer to any recurrence relation.
Example: Fibonacci relation Fn = Fn-1+ Fn-2
10. Define generating function.
A generating function describes an infinite sequence of numbers (an) by treating them
like the coefficients of a series expansion. The sum of this infinite series is the generating
function. Unlike an ordinary series, this formal series is allowed to diverge, meaning that the
generating function is not always a true function and the "variable" is actually
an indeterminate.
The generating function for 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., whose ordinary generating function is
∞
1
∑(𝑥)𝑛 =
1−𝑥
𝑛=0
The generating function for the geometric sequence 1, a, a2, a3, ... for any constant a:
∞
𝟏
∑(𝒂𝒙)𝒏 =
𝟏 − 𝒂𝒙
𝒏=𝟎

Part B – (5 × 𝟏𝟔 = 𝟖𝟎 marks)

11 (a) (i) Show that the maximum number of edges in a simple graph with n
vertices is n(n-1)/2. (6)

Proof: Consider a graph G with e edges and n vertices v1, v2, ..., vn. Since each edge
contributes two degrees, the sum of the degrees of all vertices in G is twice the number of
edges in G. That is,
𝑛

∑ 𝑑(𝑣𝑖 ) = 2𝑒.
𝑖=1

𝑖. 𝑒. , 𝑑(𝑣1 ) + 𝑑(𝑣2 ) … 𝑑(𝑣𝑛 ) = 2𝑒 … (1)

In a simple graph G, the maximum degree of each vertex in G can be (n-1).
∴ (1) ⇒ (𝑛 − 1) + (𝑛 − 1) + ⋯ + (𝑛 − 1) = 2𝑒
n times
𝑖. 𝑒. , (𝑛 − 1)(1 + 1 + ⋯ + 1) = 2𝑒
n times
⇒ (𝑛 − 1)(𝑛) = 2𝑒
𝑛(𝑛 − 1)
𝑒=
2
Therefore, the maximum number of edges in a simple graph with n vertices is n(n-1)/2. ∎

11 (a) (ii) Prove that if a graph has exactly two vertices of odd degree, there must be
path joining these two vertices. (5)
Proof: Let G be a graph with all even vertices except vertices v1, and v2, which are odd.
By the Theorem “A graph G is disconnected if and only if its vertex set V can be
partitioned into two nonempty, disjoint subsets V1 and V2 such that there exists no edge in G
whose one end vertex is in subset V1 and the other in subset V2”, which holds for every graph.
Therefore for every component of a disconnected graph, no graph can have an odd
number of odd vertices.
Therefore, in graph G, v1 and v2 must belong to the same component, and hence must
have a path between them. ∎

11 (a) (iii) Prove that any two simple connected graphs with n vertices, all of degree
two, are isomorphic. (5)

Consider a graph G with e edges and n vertices v1, v2, ..., vn. Since each edge
contributes two degrees, the sum of the degrees of all vertices in G is twice the number of
edges in G. That is,
𝑛

∑ 𝑑(𝑣𝑖 ) = 2𝑒. … (1)

𝑖=1
i.e., Sum of the degree of all vertices in graph G is twice number of edges.
Since we have n vertices of degree 2, (1) ⇒ 2𝑛 = 2𝑒 … (2)
Let G1 and G2 be two graphs having “n” vertices and each vertex is of degree 2.
Therefore both G1 and G2 will have
1. n number of vertices.
2. n number of edges.
3. Degree of all vertices is 2.
4. Since all vertices have same degree adjacency is also preserved.
More general
If two graphs G1 and G2 are having same number of vertices same number of edges and each
vertices having same degree then G1 and G2 are isomorphic graph.
And
If two graphs G1 and G2 having same number of vertices and degree of each vertex is same
then number of edges in both graph will be same.
Also
If two graphs having same number of edges and degree of each vertices is same then both
graph will have same number of vertices.
The two graphs G1 and G2 must be cycle of length n.
Therefore, any two simple connected graphs with n vertices, all of degree two, are
isomorphic to each other. ∎
Or
11 (b) (i) Mention some of the properties of tree. (5)
Properties of tree:
7. There is one and only one path between every pair of vertices in a tree T.
 8. In a graph G there is one and only one path between every pair of vertices, G
is a tree.
9. A tree with n vertices has n-1 edges.
10. Any connected graph with n vertices has n-1 edges is a tree.
11. A graph is a tree if and only if it is minimally connected.
12. A graph G with n vertices has n-1 edges and no circuits are connected.
Or
A graph G with n vertices is called a tree if
1. G is connected and is circuitless, or
2. G is connected and has n — 1 edges, or
3. G is circuitless and has n — 1 edges, or
4. There is exactly one path between every pair of vertices in G, or
5. C is a minimally connected graph.

11 (b) (ii) Prove that in any tree, there are atleast two pendant vertices. (5)

Let T be a tree, i.e., the tree T is connected, so there are no vertices of degree zero.
Suppose for a contradiction that there are n vertices with (n – 1) vertices have degree at least
two.
Then the sum of the degrees of the vertices is at least 1 + 2(n −1) = 2n −1, so the
number of edges (which is always one half the sum of the degrees) is at least (n – 1)/2.
This is impossible as a tree has exactly n − 1 edges.
Therefore, atleast there are two vertices of degree 1.
i.e., In any tree, there are atleast two pendant vertices. ∎

11 (b) (iii) Show that a Hamiltonian path is a spanning tree. (6)

Let G be a connected graph with n vertices and H be a Hamiltonian path of G.
So H visits each vertex of G exactly once.
i.e., H is a path of length n-1 with n vertices. So, H is a tree (by the property of tree).
H is a connected sub graph of G and contains all vertices of G with n-1 edges.
i.e., H is a spanning tree.
So, Hamiltonian path is a spanning tree. ∎

12 (a) (i) Explain max-flow min-cut theorem. (10)

The maximum flow possible between two vertices a and b in a network is equal to the
minimum of the capacities of all cut-sets with respect to a and b.

Proof: Consider any cut-set S with respect to vertices a and b in G. In the sub-graph G - S
(the subgraph left after removing S from G) there is no path between a and b. Therefore,
every path in G between a and b must contain at least one edge of S. Thus every flow from a
to b (or from b to a) must pass through one or more edges of S. Hence the total flow rate
between these two vertices cannot exceed the capacity of S. Since this holds for all cut-sets
with respect to a and b), the flow rate cannot exceed the minimum of their capacities. ■
12 (a) (ii) Explain about Fundamental cut set and Fundamental circuit in a graph. (6)
Adding just one edge to a spanning tree will create a cycle; such a cycle is called
a fundamental cycle (Fundamental circuits). There is a distinct fundamental cycle for each
edge; thus, there is a one-to-one correspondence between fundamental cycles and edges not
in the spanning tree. For a connected graph with V vertices, any spanning tree will have V − 1
edges, and thus, a graph of E edges and one of its spanning trees will have E − V + 1
fundamental cycles.
Dual to the notion of a fundamental cycle is the notion of a fundamental cut-set. By
deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets.
The fundamental cut-set is defined as the set of edges that must be removed from the
graph G to accomplish the same partition. Thus, each spanning tree defines a set of V − 1
fundamental cut-sets, one for each edge of the spanning tree.
Consider a spanning tree T in a given connected graph G. Let ci, be a chord with
respect to T, and let the fundamental circuit made by ci be called Γ, consisting of k branches
b1, b2, …, bk in addition to the chord ci; that is, Γ = { ci, b1, b2, b3 ..... bk} is a fundamental
circuit with respect to T. Every branch of any spanning tree has a fundamental cut-set
associated with it.
Let S1 be the fundamental cut-set associated with b1 consisting of q chords in addition
to the branch b1; that is, S1 = {b1, c1, c2, …, cq} is a fundamental cut-set with respect to T.
Because of above Theorem “Every circuit has an even number of edges in common
with any cut set”, there must be an even number of edges common to Γ and S1. Edge b1 is in
both Γ and S1 and there is only one other edge in Γ (which is ci) that can possibly also be in
Si. Therefore, we must have two edges b, and ci common to S1 and Γ. Thus the chord ci is one
of the chords c1, c2, …, cq.
Exactly the same argument holds for fundamental cut-sets associated with b2, b3, …,
and bk. Therefore, the chord ci is contained in every fundamental cut-set associated with
branches in Γ. Is it possible for the chord ci to be in any other fundamental cut-set S' (with
respect to T, of course) besides those associated with b1, b2, …, and bk?. The answer is no.
Otherwise (since none of the branches in Γ are in S'), there would be only one edge ci
common to S' and Γ, a contradiction to Theorem. Thus we have an important result.
Or
12 (b) (i) Prove that every connected graph has atleast one spanning tree. (6)
Proof: Let G be a connected graph. If G has no cycles, then it is its own spanning tree. If G
has cycles, then on deleting one edge from each of the cycles, the graph remains connected
and cycle free containing all the vertices of G. Therefore every connected graph has at least
one spanning tree. Every connected graph has at least one spanning tree.

Example: The following graph (with n = 7, e = 14), has six tree branches and eight chords
with respect to the spanning tree (bi, b2, b3, b4, b6).

12 (b) (ii) Prove the graphs K5 and K3,3 are non planar. (10)
K5 is non planar
 Euler’s Formula: Let G = (V, E) be a connected planar graph, and let n = |V |, e = |E|,
and r = number of regions in which some given embedding of G divides the plane.
Then: n − e + r = 2 . Note that this implies that all plane embeddings of a given graph
define the same number of regions.
. Let G = (V, E) be a simple connected planar graph with v vertices, e ≥ 3 edges and r
regions. Then 3r ≤ 2e and e ≤3n − 6.
Assume K5 is planar graph.

In K5, we have n = 5 and e = 10,

Hence, 3n − 6 = 15 – 6 = 9 < e = 10, which contradicts the previous result.
Therefore, our assumption is wrong. i.e., K5 is non planar graph.
K3,3 is non planar
Assume K3,3 is planar graph.

In K3,3, we have n = 6 and e = 9.

If K3,3 is planar, from Euler’s formula we would have r = 5 (r=2+e-n=2+9-6=5).
On the other hand, each region is bounded by at least four edges,
so 4r ≤ 2e, i.e., 20 ≤ 18, which is a contradiction.
Therefore, our assumption is wrong. i.e., K3,3 is non planar graph.

13 (a) (i) Prove- that every tree with two or more vertices is 2-chromatic. (5)
Proof: Select any vertex v in the given tree T. Consider T as a rooted tree at vertex v. Paint v
with color 1. Paint all vertices adjacent to v with color 2. Next, paint the vertices adjacent to
these (those that just have been colored with 2) using color 1. Continue this process till every
vertex in T has been painted. (as shown in figure). Now in T we find that all vertices at odd
distances from it have color 2, while it and vertices at even distances from it have color 1.

Now along any path in T the vertices are of alternating colors. Since there is one and only one
path between any two vertices in a tree, no two adjacent vertices have the same color. Thus T
has been properly colored with two colors. One color would not have been enough. ■
13 (a) (ii) Prove that a graph of n vertices is a complete graph iff its chromatic
polynomial is Pn(λ) = λ (λ – 1) (λ – 2) … (λ - n + 1) . (6)
Proof: With λ colors, there are λ different ways of coloring any selected vertex of a graph.
A second vertex can be colored properly in exactly 𝜆 − 1 ways,
the third in 𝜆 − 2 ways, the fourth in 𝜆 − 3 ways, ..., and
the nth in 𝜆 – 𝑛 + 1 ways if and only if every vertex is adjacent to every other.
That is, if and only if the graph is complete. ■

13 (a) (iii) Prove that a covering g of a graph is minimal iff g contains no paths of
length three or more. (5)
Proof: Suppose that a covering g contains a path of length three, and it is v1e1v2e2v3e3v4.
Edge e2 can be removed without leaving its end vertices v2 and v3 uncovered.
Therefore, g is not a minimal covering.
Conversely, if a covering g contains no path of length three or more, all its
components must be star graphs (i.e., graphs in the shape of stars; see Figure).

Figure represents Star graphs of one, two, three, and four edges.
From a star graph no edge can be removed without leaving a vertex uncovered. That is, g
must be a minimal covering. ■
Or
13 (b) (i) Explain Euler digraph. (10)
In a digraph G, a closed directed walk which traverses every edge of G exactly once is called
a directed Euler line. A digraph containing a directed Euler line is called an Euler digraph.
For example,

It contains directed Euler line a b c d e f.

Theorem: A digraph G is an Euler digraph if and only if G is connected and is balanced.

- +
[i.e., d (v) = d (v) for every vertex v in G]
Proof:
Necessity Let G be an Eulerian digraph. Therefore, it contains an Eulerian walk, say W. In
traversing W, every time a vertex v is encountered we pass along an arc incident towards v
and then an arc incident away from v. This is true for all the vertices of W, including the
initial vertex of W, say v, because we began W by traversing an arc incident away from v and
ended W by traversing an arc incident towards v.

Sufficiency Let for every vertex v in G, d-(v) = d+(v). For any arbitrary vertex v in G, we
identify a walk, starting at v and traversing the arcs of G at most once each. This traversing is
continued till it is impossible to traverse further. Since every vertex has the same number of
arcs incident towards it as away from it, we can leave any vertex that we enter along the walk
and the traversal then stops at v.
Let the walk traversed so far be denoted by W. If W includes all arcs of A, then the
result follows. If not, we remove from G all the arcs of W and consider the remainder of A.
By assumption, each vertex in the remaining digraph, say G1, is such that the number
of arcs directed towards it equals the number of arcs directed away from it. Further, W and
G1 have a vertex, say u in common, since G is connected. Starting at u, we repeat the process
of tracing a walk in G1. If this walk does not contain all the arcs of G1, the process is repeated
until a closed walk that traverses each of the arcs of G exactly once is obtained. Hence G is
Eulerian.

13 (b) (ii) Discuss about some types of digraph with suitable example. (6)
Simple Digraphs:
A digraph that has no self-loop or parallel edges is called a simple digraph.

Asymmetric Digraphs:
Digraphs that have at most one directed edge between a pair of vertices, but are
allowed to have self-loops, are called asymmetric or antisymmetric.

Symmetric Digraphs:
Digraphs in which for every edge (a, b) (i.e., from vertex a to b) there is also an edge
(b, a). A digraph that is both simple and symmetric is called a simple symmetric digraph.
Similarly, a digraph that is both simple and asymmetric is simple asymmetric.

Complete Digraphs:
A complete undirected graph was defined as a simple graph in which every vertex is
joined to every other vertex exactly by one edge. For digraphs we have two types of complete
graphs (complete symmetric and asymmetric digraph).

A complete symmetric digraph is a simple digraph in which there is exactly one edge
directed from every vertex to every other vertex, and a complete asymmetric digraph is an
asymmetric digraph in which there is exactly one edge between every pair of vertices.

A complete asymmetric digraph of n vertices contains n(n - 1)/2 edges, but a complete
symmetric digraph of n vertices contains n(n - 1) edges. A complete asymmetric digraph is
also called a tournament or a complete tournament (the reason for this term will be made
clear).

A digraph is said to be balanced if for every vertex v, the in-degree equals the out-degree;
that is, d+(vi) = d-(vi). (A balanced digraph is also referred to as a pseudo symmetric digraph.
or an isograph.) A balanced digraph is said to be regular if every vertex has the same in-
degree and out-degree as every other vertex.
Complete symmetric digraph of four vertices

14 (a) (i) How many arrangements are there of all the vowels adjacent in
SOCIOLOGICAL? (4)
Now, we may denote by X = {X1, X2, · · · Xn} the set of permutations of the vowels
O, O, O, I, I, and A. It is easy to see that n (the total number of the permutations of the
vowels in SOCIOLOGICAL) is equal to 6! / 3!2!1! = 720 / 12 = 60.
Now, let Xi , i = 1, · · · 60, be an arbitrary permutation in X. Thus any permutation of
the letters S, C, C, L, L, G and Xi corresponds to a permutation of the letters in
SOCIOLOGICAL in which all the vowels are adjacent, and this can be done in 7! /
1!2!2!1!1! = 5040 / 4 = 1260 ways.
Since there are 60 Xi , and for each of them there are 1260 distinct permutations of
the letters in SOCIOLOGICAL, in which all the vowels are adjacent, totally in 60 · 1260 =
75600 of the arrangements of the letters in SOCIOLOGICAL, all the vowels are adjacent.

14 (a) (ii) Find the value of n for the following: 2P(n, 2) + 50 = P(2n,2) (5)

14 (a) (iii) How many distinct four-digit integers can one make from the digits 1, 3,
3, 7, 7 and 8? (4)
Case #1 - Digits are 1, 3, 7 and 8 (Distinct) => 4! or 24 ways.
Case #2 - Digits are 3, 3, m, n where m != n, i.e. m and n are distinct.
3,3,_,_
3,_,3,_
 3,_,_,3 Digits to choose from for the other 2 positions are 1, 7 or 8.
_,3,3,_
_,3,_,3
_,_,3,3 3 choices for 1st slot, 2 for 2nd slot

So there are P(3,2) = 6 different numbers of the form 3,3,m,n or 33mn,

where m != n and we have 3 choices (1, 7 or 8) for digit m, and 2 choices left for digit n.
And there are P(3,2) for each of the other 5 forms, where the 3s are placed 1st and
3rd; 1st and 4th; 2nd and 3rd; 2nd and 4th; and 3rd and 4th.
Case #2 thus has 36 total distinct numbers (6 x 6) = 36
Case #3 - Digits are 7, 7, m, n where m != n, i.e. m and n are distinct.
Identical situation to case #2 above. 36 is the total.
Case #4 - Digits are 3, 3, 7 and 7.

4! 4(3)(2)(1)
-------- = ---------- = 6 ways or distinct numbers
(2!)(2!) 4
The answer is then the sum of all the values for the 4 cases.

24 + 36 + 36 + 6 = 30 + 72 = 102 distinct ways of numbers.

14 (a) (iv) In how many possible ways could a student answer a 10-question true-
false test? (3)
Each question can be answered in 2 different ways (Either true or false), and the
answer for one question has no effect on the answer for another (they are independent
events).
1st question can be answered in 2 different ways.
2nd question can be answered in 2 different ways.
….
10th question can be answered in 2 different ways.

So, the number of different ways that 10 questions can be answered

=2.2.2.2.2.2.2.2.2.2 = 210 = 1024.
Or
14 (b) (i) How many arrangements of the letters in MISSISSIPPI has no
consecutive S's? (4)
Use complementary counting.
First find the total ways to arrange the letters in MISSISSIPPI. This would be 11!/(4!4!2!).Then
subtract from that number all the ways the 2 P's are together to get the ways the P's are NOT
together. This would be done by again treating PP as one unit, so the total number of
arrangements would be 10!/(4!4!).
The answer = Total arrangents − arrangements of atlest 2 S’s=7350
Use direct counting.
Start with a string of seven stars for the letters not equal to "S". Now drop the four "S"s into the
spaces between these stars, including one or both endpoints; for example: S∗∗∗S∗S∗∗S∗S∗.
There are 8C4 = 70 ways to make this choice.
Now that we know where the "S"s go, let's fill in the seven stars with the remaining letters. There
are 7!/4!2!=105 distinct ways to fill those places.
The total number of arrangements with non-consecutive "S"s is 70⋅105=735070⋅105=7350.

Use product rule.

Seven letters except S can be arranged in 7!/4!2!1!=105 ways.
There are 8 possible locations for 4S’s. these can be chosen in 8C4 =70 ways.
The number of arrangements of MISSISSIPPI with no consecutive S’s = 105*70 = 7350

14 (b) (ii) A gym coach must select 11 seniors to play on a football team. If he can
make his selection in 12,376 ways, how many seniors are eligible to play?
(4)
Given C(n, 11) = 12,376
n!
--------------- = 12,376
(n-11)! 11!
The factors of 12,376 are: 2 x 2 x 2 x 7 x 13 x 17, so I highly suspect the answer is 17.

17! 17 x 16 x 15 x 14 x 13 x 12
-------- = ------------------------------------- = 17 x 2 x 1 x 7 x 13 x 4 = 12,376
6! 11! 6x5x4x3x2x1
The coach was choosing from 17 eligible seniors to get the 11 players.

14 (b) (iii) How many permutations of size 3 can one produce with letters m, r a, f
and t? (4)
Permutations of size 3 out of 5 letters =5P3= 5!/(5-2)!= 5 x 4 x 3 = 60

14 (b) (iv) Rama has two dozen each of n different colored beads. If she can select 20
beads (with repetitions of colors allowed), in 230,230 ways, what is he
value of n? (4)

Since he has enough beads of each color to select all 20 from a single color, the number of ways
to choose the 20 beads is

Therefore we have,

A little trial and error reveals that 230,230=26 C 20, so 19+n=26 and n=7.
15 (a) (i) Discuss about exponential generating function with an example. (10)

For a sequence a0, a1, a2, a3,, … of real numbers.

∞ 𝒊
𝑥2 𝑥3 𝒙𝒊
𝑓(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 + 𝑎3 + ⋯ = ∑ 𝒂𝒊
2! 3! 𝒊!
𝒊=𝟎
is called the exponential generating function for the given sequence.

Example : The generating function for the sequence (1,1,1,1,…).

Example : The generating function for the sequence (1, 2,4,8,…).

Operations

15 (a) (ii) Find the unique solution of the recurrence relation. 6an-7an-1=0, n≥1,
a3=343. (6)
Given: 6an-7an-1=0
6an = 7an-1
7
an = (6)an-1
7 7 7 2
= (6) (6)an-2 = (6) an-2
7 7 7 7 3
= (6) (6) (6)an-3= (6) an-3
…
7 𝑖
an = (6) an-i

Let us consider n-i = 3 ⇒ i = n-3

7 𝑛−3
an = (6) a3
7 𝑛−3 7 𝑛−3 7 𝑛−3 7𝑛 .
= (6) ∙ 343 = (6) ∙ 7∙ 7∙ 7 = (6) ∙ 73 = (6𝑛−3 )
7𝑛 .
an = (6𝑛−3 )
 Or
15 (b) (i) The population of Mumbai city is 6,000,000 at the end of the year 2015.
The number of immigrants is 20000n at the end of year n. the population
of the city increases at the rate of 5% per year. Use a recurrence relation
to determine the population of the city at the end of 2025. (8)
15 (b) (ii) Write short note on Summation operator. (8)
Maclaurin series expansion of ex and e-x.
𝑥
𝑥2 𝑥3 𝑥4
𝑒 =1+𝑥+ + + +⋯
2! 3! 4!
−𝑥
𝑥2 𝑥3 𝑥4
𝑒 = 1−𝑥+ − + −⋯
2! 3! 4!
Adding these two series together, we get,
𝑥2 𝑥4
𝑒 𝑥 + 𝑒 −𝑥 = 2(1 + + + ⋯ )
2! 4!
𝑒 𝑥 + 𝑒 −𝑥 𝑥2 𝑥4
=1+ + +⋯
2 2! 4!

Generating function for a sequence a0, a0 + a1, a0 + a1 + a2, a0 + a1 + a2 + a3,, … .

For (𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ ,, consider the function f(x)/(1-x)

𝑓(𝑥) 1
= 𝑓(𝑥). = [𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ ][1 + 𝑥 + 𝑥 2 + 𝑥 3 + ⋯ ]
1−𝑥 1−𝑥

= 𝑎0 + (𝑎0 + 𝑎1 )𝑥 + (𝑎0 + 𝑎1 +𝑎2 )𝑥 2 + +(𝑎0 + 𝑎1 +𝑎2 + 𝑎3 )𝑥 3 + ⋯

So f(x)/(1-x) generates the sequence of sums a0, a0 + a1, a0 + a1 + a2, a0 + a1 + a2 + a3,,

1/(1-x) is called the summation operator

All the Best – No substitute for hard work.

Mr. G. Appasami SET, NET, GATE, M.Sc., M.C.A., M.Phil., M.Tech., (P.hd.), MISTE, MIETE, AMIE, MCSI, MIAE, MIACSIT,
MASCAP, MIARCS, MISIAM, MISCE, MIMS, MISCA, MISAET, PGDTS, PGDBA, PGDHN, PGDST, (AP / CSE / DRPEC).