For the graph given in Q. 3(b), find the number of (v2, v5)-walks of length 3.

Let G and H be any graphs such that  Is it necessary that . Justify.

Let G be a planar graph with at least 11 vertices. Show that G is nonplanar.

Starting with the cycle (v1, v2, v3, v4, v5, v1) in the following weighted K5 perform the reduction step twice to get a Hamiltonian cycle with smaller weight.

Find the thickness of the line graph of K₄.

Explain the difference between a maximal and a maximum matching, with the help of an example.

Draw an (8, 15)-graph G with χ^, (G) = 5

Let G be a graph having no isolated vertex and no induced subgraph with exactly two edges. Show that G is a complete graph.

Check whether the sequence (4, 4, 4, 3, 2, 2, 1, 1, 1) is graphic or not. If yes, draw a graph realising this degree sequence.

Define a flow on the following network, having value at least 5.

Draw the dual of the following plane graph.

Does the dual have any cut-vertex? Justify.

If G is a k-connected graph having n vertices, what is the minimum size of G? Justify .

Every 3-colourable graph contains an odd cycle. True or false? Justify.

There exists a self-complementary graph on 2023 vertices. True of false? Justify your answer.

There exists a self-complementary graph on 2023 vertices. True of false? Justify your answer.

There exists a self-complementary graph on 2023 vertices. True of false? Justify your answer.

Draw a diagram, as nice as possible, of the line graph of the Petersen graph. Write the number of vertices, the number of edges, the minimum and maximum degrees of it.

Verify the K¨onig Egarv´ary Theorem for the following graph.

Draw the complement of the following graph.

Is the complement Hamiltonian? Justify your answer.

(a) An n-vertex forest with n/2 edges has exactly n/2 trees as its components. True or false? Justify.