# IB DP Maths Topic 10.7 Subgraphs; complements of graphs HL Paper 3

## Question

The planar graph G and its complement $$G’$$ are both simple and connected.

Given that G has 6 vertices and 10 edges, show that $$G’$$ is a tree.

## Markscheme

the complete graph with 6 vertices has 15 edges so $$G’$$ has

6 vertices and 5 edges     M1A1

the number of faces in $$G’$$ , $$f = 2 + e – v = 1$$     M1A1

it is therefore a tree because $$f = 1$$     R1

Note: Accept it is a tree because $$v = e + 1$$

[5 marks]

## Examiners report

Part (a) was well answered by many candidates.

## Question

(a)     Show that, for a connected planar graph,

$v + f – e = 2.$

(b)     Assuming that $$v \geqslant 3$$, explain why, for a simple connected planar graph, $$3f \leqslant 2e$$ and hence deduce that $$e \leqslant 3v – 6$$.

(c)     The graph G and its complement $${G’}$$ are simple connected graphs, each having 12 vertices. Show that $${G}$$ and $${G’}$$ cannot both be planar.

## Markscheme

(a)     start with a graph consisting of just a single vertex     M1

for this graph, v = 1, f = 1 and e = 0, the relation is satisfied     A1

Note: Allow solutions that begin with 2 vertices and 1 edge.

to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + fe remains equal to 2     M1A1

or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + fe remains equal to 2     M1A1

therefore, however we build up the graph, the relation remains valid     R1

[7 marks]

(b)     since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face     R1

the factor 2 follows from the fact that every edge bounds (at most) 2 faces     R1

hence $$3f \leqslant 2e$$     AG

from the Euler relation, $$3f = 6 + 3e – 3v$$     M1

substitute in the inequality, $$6 + 3e – 3v \leqslant 2e$$     A1

hence $$e \leqslant 3v – 6$$     AG

[4 marks]

(c)     let G have e edges     M1

since G and $${G’}$$ have a total of $$\left( {\begin{array}{*{20}{c}} {12} \\ 2 \end{array}} \right) = 66$$ edges     A1

it follows that $${G’}$$ has 66 – e edges     A1

for planarity we require

$$e \leqslant 3 \times 12 – 6 = 30$$     M1A1

and $$66 – e \leqslant 30 \Rightarrow e \geqslant 36$$     A1

these two inequalities cannot both be met indicating that both graphs cannot be planar     R1

[7 marks]

Total [18 marks]

## Examiners report

Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.

## Question

Draw the complement of the following graph as a planar graph.

[3]
a.

A simple graph G has v vertices and e edges. The complement $$G’$$ of G has $${e’}$$ edges.

(i)     Prove that $$e \leqslant \frac{1}{2}v(v – 1)$$ .

(ii)     Find an expression for $$e + e’$$ in terms of v .

(iii)     Given that $${G’}$$ is isomorphic to G , prove that v is of the form 4n or 4n + 1 for $$n \in {\mathbb{Z}^ + }$$ .

(iv)     Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.

(v)     Prove that if $$v \geqslant 11$$ , then G and $${G’}$$ cannot both be planar.

[14]
b.

## Markscheme

as a first step, form the following graph

(M1)(A1)

make it planar

A1

[3 marks]

a.

(i)     an edge joins a pair of vertices     R1

there is a maximum of $$\left( {\begin{array}{*{20}{c}} v \\ 2 \end{array}} \right) = \frac{1}{2}v(v – 1)$$ possible unordered pairs of vertices, hence displayed result     A1AG

(ii)     an edge joins two vertices in $${G’}$$ if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs     R1

$$e + e’ = \frac{1}{2}v(v – 1)$$     A1

(iii)     the two graphs have the same number of edges     R1

$$\Rightarrow e = \frac{1}{4}v(v – 1)$$     A1

v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result     A1AG

(iv)     the required graphs have four vertices and three edges     A1

if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa     R1

if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph     A1

state it is isomorphic to its complement     A1     N2

Note: Alternative proofs are possible, but should include the final statement for full marks.

(v)     using $$e \leqslant 3v – 6$$ for planar graphs     M1

$$\frac{1}{2}v(v – 1) = e + e’ \leqslant 6v – 12$$     A1

$${v^2} – 13v + 24 \leqslant 0$$ is not possible for $$v \geqslant 11$$     R1

[14 marks]

b.

## Examiners report

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

a.

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

b.

## Question

Draw the complement of the following graph as a planar graph.

[3]
a.

A simple graph G has v vertices and e edges. The complement $$G’$$ of G has $${e’}$$ edges.

(i)     Prove that $$e \leqslant \frac{1}{2}v(v – 1)$$ .

(ii)     Find an expression for $$e + e’$$ in terms of v .

(iii)     Given that $${G’}$$ is isomorphic to G , prove that v is of the form 4n or 4n + 1 for $$n \in {\mathbb{Z}^ + }$$ .

(iv)     Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.

(v)     Prove that if $$v \geqslant 11$$ , then G and $${G’}$$ cannot both be planar.

[14]
b.

## Markscheme

as a first step, form the following graph

(M1)(A1)

make it planar

A1

[3 marks]

a.

(i)     an edge joins a pair of vertices     R1

there is a maximum of $$\left( {\begin{array}{*{20}{c}} v \\ 2 \end{array}} \right) = \frac{1}{2}v(v – 1)$$ possible unordered pairs of vertices, hence displayed result     A1AG

(ii)     an edge joins two vertices in $${G’}$$ if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs     R1

$$e + e’ = \frac{1}{2}v(v – 1)$$     A1

(iii)     the two graphs have the same number of edges     R1

$$\Rightarrow e = \frac{1}{4}v(v – 1)$$     A1

v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result     A1AG

(iv)     the required graphs have four vertices and three edges     A1

if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa     R1

if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph     A1

state it is isomorphic to its complement     A1     N2

Note: Alternative proofs are possible, but should include the final statement for full marks.

(v)     using $$e \leqslant 3v – 6$$ for planar graphs     M1

$$\frac{1}{2}v(v – 1) = e + e’ \leqslant 6v – 12$$     A1

$${v^2} – 13v + 24 \leqslant 0$$ is not possible for $$v \geqslant 11$$     R1

[14 marks]

b.

## Examiners report

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

a.

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

b.

## Question

The graph $${K_{2,{\text{ }}2}}$$ is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.

Draw $${K_{2,{\text{ }}2}}$$ as a planar graph.

[2]
a.

Draw a spanning tree for $${K_{2,{\text{ }}2}}$$.

[1]
b.

Draw the graph of the complement of $${K_{2,{\text{ }}2}}$$.

[1]
c.

Show that the complement of any complete bipartite graph does not possess a spanning tree.

[3]
d.

## Markscheme

A1A1

Note:     Award A1 for a correct version of $${K_{2,{\text{ }}2}}$$ and A1 for a correct planar representation.

[2 marks]

a.

A1

[1 mark]

b.

A1

[1 mark]

c.

the complete bipartite graph $${K_{m,{\text{ }}n}}$$ has two subsets of vertices $$A$$ and $$B$$, such that each element of $$A$$ is connected to every element of $$B$$     A1

in the complement, no element of $$A$$ is connected to any element of $$B$$. The complement is not a connected graph     A1

by definition a tree is connected     R1

hence the complement of any complete bipartite graph does not possess a spanning tree     AG

[3 marks]

Total [7 marks]

d.

## Examiners report

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for $${K_{2,2}}$$. Some candidates, however, produced a correct non-planar representation of $${K_{2,2}}$$.

a.

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for $${K_{2,2}}$$ and the correct complement of $${K_{2,2}}$$.

b.

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for $${K_{2,2}}$$ and the correct complement of $${K_{2,2}}$$.

c.

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of $${K_{m,n}}$$ does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.

d.