1. State whether the following statements are true or false. Justify your answers with appropriate arguments or illustrations.

(a) If G and H are two simple graphs and u is an isomorphism from G onto then there exist two adjacent vertices u and v in G such that and are adjacent in H. Every maximal trail in an even graph is closed. A graph with n vertices and n edges is always a tree. For kEN, every k-regular bipartite graph has a perfect matching. K4 is outer planar.

2.(a) Show that there is no 4-regular bipartite graph with 15 vertices.
Prove that a graph is Eulerian if and only if it has at most one non-trivial component and all its vertices are of even degree.

3.(a) Let d be a list of natural numbers, of length and be the list obtained by eliminating the largest element and subtracting 1 from its next largest numbers. Prove that d is graphic if and only if is graphic.
Find the chromatic number of the following graph <img src='./qimages/12501-3b.jpg'>

Also, give a minimal colouring of the graph.

4.(a) Prove that every tree with at least two vertices has at least two leaves. State and prove the Cayley's formula for the number of trees with n vertices.

(c) Check whether the following graph is Hamiltonian <img src='./qimages/12501-4c.jpg'>

Justify your answer.

5.(a) If G is a bipartite graph, then prove that the maximum size of a matching in G equals the minimum size of a vertex cover of G.
Find the minimum spanning tree for the following graph using Kruskal's algorithm. <img src='./qimages/12501-5b.jpg'>

Does this graph. have a. unique minimal spanning tree? Justify your answer.

6.(a) If G is a 2-connected graph, then show that obtained by subdividing an edge of is also 2-connected. Find a non-zero, feasible flow in the network given below: <img src='./qimages/12501-6b.jpg'>

7.(a) Prove that X 1.
State and prove Euler's formula.
Identify the cut vertices and cut edges of the following graph:
<img src='./qimages/12501-7c.jpg'>

Also draw the sub-graphs obtained by removing the vertex v3,

(ii) the edge v3v5.