Graph Theory  past/Previous question paper

Graph Theory Fall 21 in past paper

Q1: Answer the following short questions

i) Define Planar Graph with example.

(5×2=10)

ii) Make a bipartite graph which is 5 regular.

iii) Find the chromatic polynomial of k2,5

iv) Define chromatic index. Find chromatic index for kr.

v) Give two examples of graphs which are Eulerian as well as Hamiltonian.

Q2: Define the following with one example each.(10)

i) Incidence matrix

ii) Bipartite Graph

iii)Spanning subgraph

iv) Hamiltonian Graph

v) Cut vertex

Q 3:(10)

i) Find four Hamiltonian cycles in ks, no two of which have an edge in

common.

ii) Make a graph G of order 6 and size 10 in which the minimum degree is 3 and the maximum degree is 4.