Graph Theory and Combinatorics — Summer 2023

Define following terms:

Connected Graph ii) Closed walk iii) Euler Trail

Give an example of a connected graph that has

Neither an Euler circuit nor a Hamilton Cycle. ii) An Euler circuit but no Hamilton cycle. iii) A Hamilton cycle but no Euler circuit. iv) Both a Hamilton cycle and Euler circuit.

Define prefix code. Construct an optimal prefix code for the symbols A, B, C, D, E, F, G, H, I, Jthat occur with respective frequencies 78, 16, 30, 35, 125, 31, 20, 50, 80, 3.

Explain isomorphism of graphs. Determine whether or not the following graphs are isomorphic.

Describe The Seven Bridges of Konigsberg.

Define planar graph. If a connected planar graph Ghas n vertices, e edges, r regions than prove that n – e + r = 2.

Define chromatic number and chromatic polynomial. Determine the chromatic polynomial for the graph shown in figure.1

Find the dual for the given planar graph.

Define a tree. Prove that tree with Pvertices has P – 1 edges.

State and prove Max – Flow and Min – cut theorem.

Show that Peterson graph is a non planar graph.

Define and give an example for each of the following:

Complete Binary Tree ii) Balanced Tree

Find the maximum flow and the corresponding minimum cut for the transport network shown below:

Determine the coefficient of a5b2 in expansion of (2a – 3b)7.

How many arrangements are there for all letters in the word SOCIOLOGICAL? In how many of these arrangements:

Aand Gare adjacent ii) All the vowels are adjacent.

Astudent is to answer seven out of 10 questions on an examination. In how many ways can he make his selection if

There are no restrictions? ii) He must answer the first two questions? iii) He must answer at least four of the first six questions?

Determine the coefficient of x2yz2 in expansion of [(x/2) + y – 3z]5.

How many derangements are there for 1, 2, 3, 4, 5 ?

Find the exponential generating function for each of the following sequences:

1, -1, 1, -1, 1, -1, ……… ii) 1, 22, 23, 24,…….. iii) 1, -a, a2, -a3, a4,…………..., a ∈ R

Find the coefficient of x5 in (1 – 2x)-7.

Find generating function for the recurrence relation: a - 3a + 2a = 0, n ≥ 0, with a = 1, a = 6. n+2 n+1 n 0 1

Solve the recurrence relation a = 7a , where n ≥ 1 and a = 98. n n-1

Show that (1 – 4x)-1/2 generates the sequence (2n), n ∈ N. n

Define generating function. In how many ways can a police captain distribute 24 rifle shells to four police officers so that each officer gets at least three shells, but not more than eight?