www.vidyarthiplus.

com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

  

  
n n n n
a n 1 x  2 an x  4 x  0
n0 n0 n0

1  3x
G (x) 
(1  2 x ) (1  4 x )
1 1
By Applying Partial fractions we get A  ,B 
2 2
 
1 1
 
n n n n
G (x)  2 x  4 x
2 n0
2 n0

hence w e get
n 1 n 1
an  2  2(4)
10(b) Find the generating function of Fibonacci sequence.
Solution
Fibonacci sequence : f n  f n  1  f n  2 , n  2 with f o  0 , f 1  1
Multiply by z n , and sum over all n  2 .
  

   f n 1 z  
n n n
fn z fn2 z
n2 n2 n2

G ( z )  f 0  f 1 z  z ( G (z )  f 0 )  z ( G ( z ))
2

G (z)  
n
fn z
n0

Where ( i .e ) G ( z )  z G ( z )  z G ( z )  f 0  f 1 z  z f 0
2

z
G (z) 
1 z  z
2

UNIT III GRAPH THEORY

PART – A
01. Define Graph.
Ans: A graph G = (V,E) consists of a finite non empty set V, the element of which are the vertices of G,
and a finite set E of unordered pairs of distinct elements of V called the edges of G.
02. Define complete graph.
Ans: A graph of n vertices having each pair of distinct vertices joined by an edge is called a Complete
graph and is denoted by Kn.
03. Define regular graph.
Ans: A graph in which each vertex has the same degree is called a regular graph. A regular graph has k –
regular if each vertex has degree k.
04. Define Bipartite Graph with example.
Ans: Let G = (V,E) be a graph. G is bipartite graph if its vertex set V can be partitioned into two nonempty
disjoint subsets V1 and V2 , called a bipartition, such that each edge has one end in V1 and in V2 . For eg
C6
V2 V3

V1 V4

V6 V5

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 20 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

05. Define complete bipartite graph with example

Ans: A complete bipartite graph is a bipartite graph with bipartition V1 and V2 in which each vertex of V1
is joined by an edge to each vertex of V2. For eg.

A1 A2

K2,3

B1 B2 B3

06. Define Subgraph.

Ans: A graph H = (V1,E1) is a subgraph of G = (V,E) provided that V1 ,E1 and for each e  E1 , both ends
of e are in V1.
07. Define Isomorphism of two graphs.
Ans: Two graphs G1 = (V1,E1) and G2 = (V2,E2) are the same or isomorphic, if there is a bijection
F :V1  V2 such that (u,v)  E1 if and only if ( F(u), F(v))  E2..
08. Define strongly connected graph.
Ans: A digraph G is said to be strongly connected if for every pair of vertices, both vertices of the pair are
reachable from one another.
09. State the necessary and sufficient conditions for the existence of an Eulerian path in a connected
graph.
Ans: A connected graph contains an Euler path if and only if it has exactly two vertices of odd degree.
10. State Handshaking theorem.
Ans: If G = (V, E) is an undirected graph with e edges, then  deg( v i )  2 e
i

11. Define adjacency matrix.

Ans: Let G = (V,E) be a graph with n vertices . An “n x n” matrix A is an adjacency matrix for G if and
1 fo r (i, j ) in E
only if for 𝑖  𝐼, 𝑗  𝑛, A (i, j )  
0 fo r (i, j ) is n o t in E

12. Define Connected graph.

Ans: A graph for which each pair of vertices is joined by a trail is connected.
13. Define Pseudo-graph.
Ans: A graph is called a pseudo-graph if it has both parallel edges and self loops.
14. Does there exist a simple graph with five vertices of the 0, 1, 2, 2, 3 degrees? If so, draw such a
graph.
Ans:

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 21 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

Yes.
15. Draw a complete bipartite graph of K2, 3 and K3, 3
Ans:
A1 A2 A3
A1 A2

K2,3 K3,3

B1 B2 B3 B1 B2 B3

16. Define spanning subgraph.

Ans: Let a graph H = (V1,E1) is a subgraph of G = (V,E). H is a spanning subgraph of G if H is a subgraph
of G with V1= V and E1  E.
17. Define Induced subgraph.
Ans: A graph H = (V1,E1) is a subgraph of G = (V,E). H is an induced subgraph of G such that E 1 consists
of all the edges of G with both ends in V1.
18. Define Eulerian Circuit.
Ans: A circuit in a graph that includes each edge exactly once, the circuit is called an Eulerian circuit.
19. State the condition for Eulerian cycle.
Ans: (i) Starting and ending pts are same.
(ii) Cycle should contain all edges of graph but exactly once
20 Show that C6 is a bipartite graph?
Ans:
C6 vertex set is partitioned into two set V1 = {v1, v3, v5} and V2 = { v2, v4, v6}, where every edge of C6 joins
a vertex in V1 to a vertex in V V V3
2

V1 V4

V6 V5

PART - B
1(a) State and prove Handshaking Theorem.
If G = (V, E) is an undirected graph with e edges, then  deg( vi )  2e
i

Proof: Since every edge is incident with exactly two vertices, every edge contributes 2 to the sum of the
degree of the vertices.
Therefore, all the e edges contribute (2e) to the sum of the degrees of the vertices.
Hence  deg( v i )  2 e .
i

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 22 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

1(b) In any graph show that the number of odd vertices is even.
Let G = (V, E) be the undirected graph. Let 𝑣1 and 𝑣2 be the set of vertices of G of even and odd degrees
respectively. Then by hand shaking theorem,
2e =  d e g ( v i )   d e g ( v j ) . Since each deg(vi) is even,  d e g ( v i ) is even. Since LHS is even, we
v i  v1 v j v2 v i  v1

get  deg(v j ) is even. Since each deg(vj) is odd, the number of terms contain in  deg(v j ) or v2 is
v j v2 v j v2

even, that is, the number of vertices of odd degree is even.

2(a) Prove that a simple graph with at least two vertices has at least two vertices of same degree.
Proof:
Let G be a simple graph with n  2 vertices.
The graph G has no loop and parallel edges. Hence the degree of each vertex is  n-1.
Suppose that all the vertices of G are of different degrees.
Following degrees 0, 1, 2, …, n-1 are possible for n vertices of G.
Let u be the vertex with degree 0. Then u is an isolated vertex.
Let v be the vertex with degree n-1 then v has n-1 adjacent vertices.
Because v is not an adjacent vertex of itself, therefore every vertex of G other than u is an adjacent vertex
of G.
Hence u cannot be an isolated vertex, this contradiction proves that simple graph contains two vertices of
same degree.
2(b) n ( n  1)
Prove that the maximum number of edges in a simple graph with n vertices is n c  2
2
Proof:
We prove this theorem, by the method of mathematical induction. For 𝑛 = 1, a graph with 1 vertex has
no edges. Therefore the result is true for n = 1.
For n = 2, a graph with two vertices may have atmost one edge. Therefore 2 (2 –1) / 2 = 1.
Hence for n = 2, the result is true.
k ( k  1)
Assume that the result is true for n = k, i.e, a graph with k vertices has atmost edges.
2
Then for n = k + 1, let G be a graph having n vertices and G be the graph obtained from G, by deleting one
vertex say, „v‟  V(G).
k ( k  1)
Since G has k vertices then by the hypothesis, G has atmost edges. Now add the vertex v to G.
2
„v‟ may be adjacent to all the k vertices of G.
k ( k  1) k ( k  1)
Therefore the total number of edges in G are +k= .
2 2
Therefore the result is true for n = k+1.
n ( n  1)
Hence, the maximum number of edges in a simple graph with „n‟ vertices is .
2
3(a) ( n  1 )(n  2 )
Show that a simple graph G with n vertices is connected if it has more than edges
2
Proof:
Suppose G is not connected. Then it has a component of k vertices for some k,
The most edges G could have is

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 23 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

k ( k  1)  ( n  k )( n  k  1)
C (k , 2)  C (n  k , 2) 
2
2
2 n n
k  nk 
2
This quadratic function of f is minimized at k = n/2 and maximized at k = 1 or k = n – 1
Hence, if G is not connected, then the number of edges does not exceed the value of this function at 1 and
( n  1)(n  2 )
at n-1, namely .
2
3(b) If a graph G has exactly two vertices of odd degree, then prove that there is a path joining these two
vertices.
Proof:
Case (i): Let G be connected.
Let v1 and v2 be the only vertices of G with are of odd degree. But we know that number of odd vertices is
even. So clearly there is a path connecting v1 and v2, because G is connected.
Case (ii): Let G be disconnected
Then the components of G are connected. Hence v1 and v2 should belong to the same component of G.
Hence, there is a path between v1 and v2.
4(a) ( n  k )( n  k  1 )
Prove that a simple graph with n vertices and k components can have at most
2
edges.
Let the number of vertices of the ith component of G be 𝑛𝑖 , 𝑛𝑖 ≥ 1..
k k

 ni  n   ( n i  1)  ( n  k )
i 1 i 1

2
 k


2 2
Then   ( n i  1)   n  2nk  k
 i 1 
k k

 
2 2 2 2 2 2
th a t is ( n i  1) n  2nk  k  ni  n  2nk  k  2n  k
i 1 i 1

n i ( n i  1) 1
k
n

2
Now the maximum number of edges in the ith component of G =  ni 
2 2 i 1
2
2 2
(n  2nk  k  2n  k ) n ( n  k )( n  k  1)
  
2 2 2
4(b) If all the vertices of an undirected graph are each of degree k, show that the number of edges of the
graph is a multiple of k.
Solution: Let 2n be the number of vertices of the given graph….(1)
Let n e be the number of edges of the given graph.
By Handshaking theorem, we have
2n

 d eg vi  2 ne
i 1

2 nk  2 ne (1)

ne  nk
Number of edges =multiple of 𝑘.
Hence the number of edges of the graph is a multiple of k

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 24 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

5(a) Draw the graph with 3 vertices A,B,C, D & E such that the deg(A)=3,B is an odd vertex, deg(C)=2
and D and E are adjacent.
Solution:
d(E)=5 ,d(C)=2,d(D)=5 ,d(A)=3 d(B)=1

5(b) Draw the complete graph K 5 with vertices A,B,C,D,E. Draw all complete sub graph of K 5 with 4
vertices.
Solution:

complete sub graph with 4 vertices

6(a) Prove that a given connected graph G is Euler graph if and only if all vertices of G are of even
degree.
Solution:
Case (i) Prove If G is Euler graph→ Every vertex of G has even degree.
Case (ii) Prove If Every vertex of G has even degree.→ G is Euler graph ( by Contradiction Method).

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 25 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

6(b) Find the adjacency matrix of the given directed graph.

(i) (ii)

Answer:
 0 2 0 0 0 0
 
1 1 0 1

2 0 1 1 0 0

 
0 0 0 1  0 1 2 1 0 0
 
(i) ( ii )  
0 0 0 0 0 1 1 2 0 0

 
 3
1 0 1 0 0 0 0 0 0
 
 
 0 0 0 1 3 0
7(a) Show that isomorphism of simple graphs is an equivalence relation. [November 2014]
Solution:
G is isomorphism to itself by the identity function, So isomorphism is reflexive. Suppose that G is
isomorphic to H.Then there exists a one –to-one correspondence f from G to H that preserves adjacency
1
and nonadjacency.It follows that f is a one-to-one correspondence from H to G that preserves adjacency
and non-adjacency.Hence isomorphism is symmetric.If G is isomorphic to H and H is isomorphic to K then
there are ono-to-one correspondences f and g from G to H and from H to K that preserves adjacency and
nonadjacency.It follows that g  f is a one-to-one correspondencies from G to K that preserves adjacency
and non-adjacency.Hence isomorphism is transitive.
7(b) Find the incidence matrix for the following graph.

(i) (ii)

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 26 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

Answer:

1 1 1 0 0 0 1 0 1
   
0 0 1 1 0 1 0 1 0
(i )   ( ii )  
1 0 0 0 1 0 1 0 1
   
0 1 0 1 0 1 0 1 0

8(a) Examine whether the following pair of graphs are isomorphic. If not isomorphic, give the reasons

u1 u2 v1
v2
v5
u3
u5 u4
v4 v3

Solution:
Same number of vertices and edges. Also an equal number of vertices with a given degree.
The adjacency matrices of the two graphs are

0 1 0 1 1
  0 1 0 1 1
1 0 1 1 1  
  1 0 1 1 1
0 1 0 1 0
  0
1
and 1 0 1 0
1 1 0 1  
  1 1 1 0 1
1 1 0 1 0
 
1 1 0 1 0
since the two adjacency matrices are the same, the two graphs are isomorphic.

8(b) Prove that if a graph G has not more than two vertices of odd degree, then there can be Euler path in
G.
Statement: Let the odd degree vertices be labeled as V and W in any arbitrary order. Add an edge to G
between the vertex pair (V,W) to form a new graph G‟.

Now every vertex of G‟ is of even degree and hence G‟ has an Eulerian Trail T.
If the edge that we added to G is now removed from T, It will split into an open trail containing all edges of
G which is nothing but an Euler path in G

9(a) Show that K 7 has Hamiltonian graph. How many edge disjoint Hamiltonian cycles are there in K 7 ?
List all the edge-disjoint Hamiltonian cycles. Is it Eulerian graph ?

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 27 ISO 9001:2008
www.vidyarthiplus.com
 www.vidyarthiplus.com
Name & Code: Discrete Mathematics, MA6566 dept of mathematics Academic Year: 2015-2016

Solution: The Graph of K 7

K7 has two edges disjoint Hamiltonian cycles.

The edge disjoint Hamiltonian cycles are
1_2_3_4_5_6_7_1 and 1_3_6_2_4_7_5_1
K 7 is an Eulerian graph

9(b) Let G be a simple indirected graph with n vertices. Let u and v be two non adjacent vertices in G
such that deg(u) + deg(v) ≥ n in G. Show that G is Hamiltonian if and only if G + uv is Hamiltonian.
Solution:
If G is Hamiltonian, then obviously G + uv is also Hamiltonian.
Conversely, suppose that G + uv is Hamiltonian, but G is not. Then by Dirac theorem, we have
deg(u) + deg(v) < n
which is a contradiction to our assumption.
Thus G + uv is Hamiltonian implies G is Hamiltonian.
10(a) Draw a graph that is both Eulerian and Hamiltonian.
Solution:
Example of Eulerian and Hamiltonian.

Consider the graph G

A B

D C

n G, consider the cycle A-B-C-D-A. Since the cycle contains all the edges, G is Eulerian. Moreover, since
the cycle contains all the vertices exactly once, G is Hamiltonian.
10(b) Prove that any 2 simple connected graphs with n vertices all of degree 2 are isomorphic.
Proof:
We know that total degree of a graph is given by
n

 d (V i )  2 | E |
i 1

Then |V| = number of vertices n

|E| = number of edges
Further the degree of every vertex is 2. Therefore we have,
n

 2  2|E |
i 1

2 (( n )  1  1)  2 | E |
 n | E |

Hence number of edges = number of vertices. Hence they are isomorphic.

St. Joseph’s College of Engineering / St. Joseph’s Institute of Technology Page No: 28 ISO 9001:2008
www.vidyarthiplus.com