# B Tech 6th Semester Graph Theory 2006-07

Note : Attempt all questions.

1. Attempt any four parts of the following :

(a) Define a bipartite graph. Show that the complement of a bipartite graph need not to be a bipartite.

(b) Discuss the Konigsberg Bridge Problem.

(c) Define the following with one example each:

(a) Infinite graph

(b) Hamiltonian path

(c) Component of a graph

(d) Euler graph

(e) Spanning subgraph

(d) Define isomorphic graph. Draw three isomorphic graph of the following graph.

(e) Differentiate, with example, a simple graph and a multigraph. Show that the maximum number of edges in a simple graph with n vertices n(n-l)/2.

(f)  What is the largest number of vertices in a graph with

(a) 35 edges if all vertices are of degree at least 3.

(b) 24 edges and all vertices of the same degree

2. Attempt any four parts of the following:

(a) Define binary tree and state two application of it in computer science.

(b) Apply Prime’s algorithm to find a minimal spanning tree of the following graph.

(c)   Find shortest path form Vj to v8 using Dijkstra algorithm in the following graph.

(d) Define spanning tree of a graph. Show that a Hamiltonian path in a graph is a spanning tree.

(e) Show a tree in which its diameter in not equal to twice of the radius. Under what condition does this inequality hold? Elaborate.

(f)  What are the different properties when a graph G with n vertices is called a tree?

3. Attempt any four parts of the following :

(a) Define the edge connectivity and vertex connectivity of a connected graph. Find them for the following graphs :

(b)   Show that a complete graph kn is planar if n < 4

(c) Draw a spanning tree of the following graph given below and list all the fundamental circuits with respect to this tree.

(d) Find the dual of the following graph.

(e)   Prove that a graph G has a dual if and only if it is a planar.

a)     Show, by sketching, that the thickness of eight- vertex complete graph is two.

b)    Define basis vectors of a graph. Find the number of distinct basis possible in a cut-set subspace.

c)     Define (i) reduced incidence matrix (ii) fundamental circuit matrix and (iiii) fundamental cut-set matrix, of a connected graph. Also derive the relationship between them.

d)    Consider the circuit matrix (B) and incidence matrix (A) of a simple connected graph whose columns are arranged using the same order of edges. Then prove that every row of B is orthogonal to every row of A. Also verify the result for the following graph.

4. Attempt any two parts :

(a) What do you mean by chromatic number and chromatic polynomial of a graph? Determine the chromatic number and chromatic polynomial of the following graphs.

(b) Define Euler diagraph with example. Prove that every Euler diagraph without isolated verities is strongly connected. Also, show by constructing a counter example, that converse is not true.

(c) State and prove Cayley’s theorem for counting trees.