Solved: G is a simple, connected graph with eight vertices. H is a connected, planar... [IB Mathematics Applications & Interpretation (Math AI)]

Question

HLPaper 3

$G$ is a simple, connected graph with eight vertices.

$H$ is a connected, planar graph, with $v$ vertices, $e$ edges and $f$ faces. Every face in $H$ is bounded by exactly $k$ edges.

Write down the minimum number of edges in $G$ .

[1]

Verified

Solution

7 (a tree) A1

[1 mark]

Find the maximum number of edges in $G$ .

[2]

Verified

Solution

$\frac{{8 \times 7}}{2}\left( {7 + 6 + 5 + 4 + 3 + 2 + 1} \right)$ (a complete graph) (M1)

$= 28$ A1

[2 marks]

Find the maximum number of edges in $G$ , given that $G$ contains anEulerian circuit.

[2]

Verified

Solution

$\frac{{8 \times 6}}{2}$ (since every vertex must be of degree 6) (M1)

$= 24$ A1

[2 marks]

Explain why $2e = kf$ .

[2]

Verified

Solution

counting the edges around every face gives $k f$ edges A1

but as every edge is counted in 2 faces R1

$\Rightarrow kf = 2e$ AG

[2 marks]

Find the value of $f$ when $v = 9$ and $k = 3$ .

[3]

Verified

Solution

using $v - e + f = 2$ with $v = 9$ M1

EITHER

substituting $2e = 3f$ into $2\left( 9 \right) - 2e + 2f = 4$ (M1)

substituting $e = \frac{{3f}}{2}$ into $9 - e + f = 2$ (M1)

THEN

$18 - f = 4$

$f = 14$ A1

[3 marks]

Find the possible values of $f$ when $v = 13$ .

[4]

Verified

Solution

$2v - kf + 2f = 4$ (or equivalent) M1

when $v =13$

$\left( {k - 2} \right)f = 22$ or $\left( {2 - k} \right)f = - 22$ A1

EITHER

$\left( {k - 2} \right)f = 1 \times 2 \times 11$ M1

substitutingat least two of $k = 13{\text{, }}4{\text{, }}3$ into $f = \frac{{22}}{{k - 2}}$ (or equivalent) M1

THEN

$f = 2{\text{, }}11{\text{, 22}}$ (since $f > 1$ ) A1

[4marks]

G is a simple, connected graph with eight vertices. H is a connected, planar graph, with v vertices, e edges and f faces. Every face in H is bounded by exactly k edges.

Related topics