(a)     A connected planar graph G has e edges and v vertices.

(i)     Prove that \(e \geqslant v - 1\).

(ii)     Prove that e = v −1 if and only if G is a tree.

(b)     A tree has k vertices of degree 1, two of degree 2, one of degree 3 and one of degree 4. Determine k and hence draw a tree that satisfies these conditions.

(c)     The graph H has the adjacency table given below.

\[\left( {\begin{array}{*{20}{c}}
  0&1&1&0&0&0 \\
  1&0&0&1&1&0 \\
  1&0&0&0&1&1 \\
  0&1&0&0&0&0 \\
  0&1&1&0&0&0 \\
  0&0&1&0&0&0
\end{array}} \right)\]

(i)     Explain why H cannot be a tree.

(ii)     Draw the graph of H .

(d)     Prove that a tree is a bipartite graph.

(a)     (i)     Euler’s relation is

\(e = v - 2 + f \geqslant v - 1,{\text{ as }}f \geqslant 1\)     M1A1

 

(ii)     \(G{\text{ is a tree }} \Leftrightarrow {\text{ no cycles }} \Leftrightarrow {\text{ }}f = 1\)     R1R1

[4 marks]

 

(b)     the result from (a) (ii) gives

\(e = k + 2 + 1 + 1 - 1 = k + 3\)     M1A1

for a tree we also have

\(2e = {\text{sum of degrees}}\)     M1

\(2k + 6 = k + 4 + 3 + 4 = k + 11\)

hence \(k = 5\)     A1

     A2

 

Note: Accept alternative correct solutions.

 

[6 marks]

 

(c)     (i)     \(v - 1 = 5 < 6 = e\,\,\,\,\,{\text{by (a) (ii)}}\)     M1A1

G cannot be a tree     AG

(ii)          A1

 

[3 marks]

 

(d)     take any vertex in the tree and colour it black     M1

colour all adjacent vertices white

colour all vertices adjacent to a white vertex black

continue this procedure until all vertices are coloured     M1

which must happen since the graph is connected     R1 

as the tree contains no cycles, no vertex can be both black and white and the graph is proved to be bipartite     R1

[4 marks]

Total [17 marks]

Many candidates seem only to have a weak understanding of the requirements for the proof of a mathematical statement.