(a) Find the line graph of the following graph? Write number of vertices and edges in the line graph.

(c) Prove or disprove: If G is a graph with χ(G) denoting its chromatic number, then

(b) Using Fleury’s algorithm, find an Eulerian circuit in the following graph.

(a) Find the values of n and m for which the star graph S_n,mis Eulerian.

(d) Provide an example of a 3-regular planar graph with 8-vertices. Is this graph a maximal planar graph? Why?

(c) State and prove Hall’s Theorem

Show that [S, T] is an (s, t)-cut in network N give in part(a),where Does N have an other (s, t)-cut with capacity smaller than Cap(S, T)? What is the maximum possible value of a flow in N?

(a) What is the maximum possible flow that can pass through the following network N? Define such a flow

(d) Find the matching number of the line graph of the graph given in part(a).

(c) For every graph True or false? Justify.

(b) Check whether the graph is planar or not.

(a) Verify Euler’s formula for the following plane graph.

(c) Check the sequence (6, 5, 4, 4, 3, 1, 1, 1, 1) is graphic or not. Also, find a graph realising it.

Is it possible that a graph is 3-chromatic but not 3-critical? If so, explain it with an example.

(a) Show that there are 14 spanning trees of the following graph. Draw all the spanning trees.

(d) Find the chromatic and edge-chromatic numbers of the following graph

(c) Determine the number of non-planar graphs with 6 vertices. 

(b) Find a minimum-weight spanning tree in the following graph.

(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.

Check whether the following graphs G and H are isomorphic or not.