1. State, with justification or illustration whether each of the following statements to is True or False.

Every graph with n vertices and k edges has at least n components.

There are graphs G with diam G =rad G.

Every complete graph has a perfect matching.

If G is a graph with two non-adjacent vertices u and v and G uv is Hamiltonian, then G is Hamiltonian.

If G is a simple graph with then G is planar.

Determine which pairs of graphs given below are isomorphic. Justify your answer.

<img src='./qimages/10168-2a.jpg'>

Prove that an edge e in a graph G is a cut-edge if and only if e belongs to no cycle in G.

Prove that every even graph decomposes into cycles.

Prove that if a set d2, d3, ... dn} of non-negative integers represents the degrees of vertices In a graph then,
<img src='./qimages/10168-3a.jpg'>
is even and di n for each i ..., n. Is the converse true Justify your answer.

Find the values of n for which Kn,n is Hamiltonian. Justify your answer.

If G is a self-complementary graph of order then prove that diam

The number of leaves in any tree of order

<img src='./qimages/10168-4a.jpg'>

For every graph prove that

X •

Find a maximum matching in the following graph. Justify your answer.

<img src='./qimages/10168-4c.jpg'>

Use Dijkstra's algorithm to find the shortest paths from vertex a to all other vertices, sharing all the necessary steps.

<img src='./qimages/10168-5a.jpg'>

(b)For any graph prove that

Construct a simple cubic graph having no 1-factor.

Prove that for any simple graph G and construct a graph for which and =3.

Using Mycielski's construction, produce a 4-chromatic graph from C5.