File "markSceme-SL-paper2.html"
Path: /IB QUESTIONBANKS/4 Fourth Edition - PAPER/HTML/Further Mathematics/Topic 6/markSceme-SL-paper2html
File size: 188.19 KB
MIME-type: text/html
Charset: utf-8
<!DOCTYPE html>
<html>
<meta http-equiv="content-type" content="text/html;charset=utf-8">
<head>
<meta charset="utf-8">
<title>IB Questionbank</title>
<link rel="stylesheet" media="all" href="css/application-212ef6a30de2a281f3295db168f85ac1c6eb97815f52f785535f1adfaee1ef4f.css">
<link rel="stylesheet" media="print" href="css/print-6da094505524acaa25ea39a4dd5d6130a436fc43336c0bb89199951b860e98e9.css">
<script src="js/application-13d27c3a5846e837c0ce48b604dc257852658574909702fa21f9891f7bb643ed.js"></script>
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML-full"></script>
<!--[if lt IE 9]>
<script src='https://cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv.min.js'></script>
<![endif]-->
<meta name="csrf-param" content="authenticity_token">
<meta name="csrf-token" content="iHF+M3VlRFlNEehLVICYgYgqiF8jIFlzjGNjIwqOK9cFH3ZNdavBJrv/YQpz8vcspoICfQcFHW8kSsHnJsBwfg==">
<link href="favicon.ico" rel="shortcut icon">
</head>
<body class="teacher questions-show">
<div class="navbar navbar-fixed-top">
<div class="navbar-inner">
<div class="container">
<div class="brand">
<div class="inner"><a href="http://ibo.org/">ibo.org</a></div>
</div>
<ul class="nav">
<li>
<a href="../../index.html">Home</a>
</li>
<li class="active dropdown">
<a class="dropdown-toggle" data-toggle="dropdown" href="#">
Questionbanks
<b class="caret"></b>
</a><ul class="dropdown-menu">
<li>
<a href="../../geography.html" target="_blank">DP Geography</a>
</li>
<li>
<a href="../../physics.html" target="_blank">DP Physics</a>
</li>
<li>
<a href="../../chemistry.html" target="_blank">DP Chemistry</a>
</li>
<li>
<a href="../../biology.html" target="_blank">DP Biology</a>
</li>
<li>
<a href="../../furtherMath.html" target="_blank">DP Further Mathematics HL</a>
</li>
<li>
<a href="../../mathHL.html" target="_blank">DP Mathematics HL</a>
</li>
<li>
<a href="../../mathSL.html" target="_blank">DP Mathematics SL</a>
</li>
<li>
<a href="../../mathStudies.html" target="_blank">DP Mathematical Studies</a>
</li>
</ul></li>
<!-- - if current_user.is_language_services? && !current_user.is_publishing? -->
<!-- %li= link_to "Language services", tolk_path -->
</ul>
<ul class="nav pull-right">
<li>
<a href="https://06082010.xyz">IB Documents (2) Team</a>
</li></ul>
</div>
</div>
</div>
<div class="page-content container">
<div class="row">
<div class="span24">
</div>
</div>
<div class="page-header">
<div class="row">
<div class="span16">
<p class="back-to-list">
</p>
</div>
<div class="span8" style="margin: 0 0 -19px 0;">
<img style="width: 100%;" class="qb_logo" src="images/logo.jpg" alt="Ib qb 46 logo">
</div>
</div>
</div><h2>SL Paper 2</h2><div class="specification">
<p>The sequence \(\{ {u_n}\} \) satisfies the second-degree recurrence relation</p>
<p>\[{u_{n + 2}} = {u_{n + 1}} + 6{u_n},{\text{ }}n \in {\mathbb{Z}^ + }.\]</p>
</div>
<div class="specification">
<p>Another sequence \(\{ {v_n}\} \) is such that</p>
<p>\[{v_n} = {u_{2n}},{\text{ }}n \in {\mathbb{Z}^ + }.\]</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down the auxiliary equation.</p>
<div class="marks">[1]</div>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Given that \({u_1} = 12,{\text{ }}{u_2} = 6\), show that</p>
<p>\[{u_n} = 2 \times {3^n} - 3 \times {( - 2)^n}.\]</p>
<div class="marks">[5]</div>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Determine the value of \(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n} + {u_{n - 1}}}}{{{u_n} - {u_{n - 1}}}}\).</p>
<div class="marks">[4]</div>
<div class="question_part_label">a.iii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Determine the second-degree recurrence relation satisfied by \(\{ {v_n}\} \).</p>
<div class="marks">[4]</div>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p>the auxiliary equation is \({m^2} - m - 6 = 0\) or equivalent <strong><em>A1</em></strong></p>
<p><strong><em>[??? marks]</em></strong></p>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>attempt to solve quadratic <strong><em>(M1)</em></strong></p>
<p>the roots are \(3,{\text{ }} - 2\) <strong><em>A1</em></strong></p>
<p>the general solution is</p>
<p>\({u_n} = A \times {3^n} + B \times {( - 2)^n}\) <strong><em>A1</em></strong></p>
<p>initial conditions give </p>
<p>\(3A - 2B = 12\)</p>
<p>\(9A + 4B = 6\) <strong><em>M1</em></strong></p>
<p>the solution is \(A = 2,{\text{ }}B = - 3\) <strong><em>A1</em></strong></p>
<p>\({u_n} = 2 \times {3^n} - 3 \times {( - 2)^n}\) <strong><em>AG</em></strong></p>
<p><strong><em>[??? marks]</em></strong></p>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>\({u_n} + {u_{n - 1}} = 2 \times {3^n} - 3 \times {( - 2)^n} + 2 \times {3^{n - 1}} - 3 \times {( - 2)^{n - 1}}\) <strong><em>M1</em></strong></p>
<p>\( = 8 \times {3^{n - 1}} + {\text{multiple of }}{2^{n - 1}}\) <strong><em>A1</em></strong></p>
<p>\({u_n} - {u_{n - 1}} = 2 \times {3^n} - 3 \times {( - 2)^n} - 2 \times {3^{n - 1}} + 3 \times {( - 2)^{n - 1}}\)</p>
<p>\( = 4 \times {3^{n - 1}} + {\text{multiple of }}{2^{n - 1}}\) <strong><em>A1</em></strong></p>
<p>any evidence of noting that the \({3^{n - 1}}\) terms dominate <strong><em>R1</em></strong></p>
<p>\(\mathop {\lim }\limits_{n \to \infty } \frac{{{u_n} + {u_{n - 1}}}}{{{u_n} - {u_{n - 1}}}} = 2\) <strong><em>A1</em></strong></p>
<p><strong><em>[??? marks]</em></strong></p>
<div class="question_part_label">a.iii.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>\({v_n} = 2 \times {3^{2n}} - 3 \times {( - 2)^{2n}}\) <strong><em>M1</em></strong></p>
<p>\( = 2 \times {9^n} - 3 \times {4^n}\) <strong><em>A1</em></strong></p>
<p>the auxiliary equation is</p>
<p>\({m^2} - 13m + 36 = 0\) <strong><em>A1</em></strong></p>
<p>the recurrence relation is</p>
<p>\({v_{n + 2}} = 13{v_{n + 1}} - 36{v_n}\) <strong><em>A1</em></strong></p>
<p><strong><em>[4 marks]</em></strong></p>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.iii.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p>In 1985 , the deer population in a national park was \(330\). A year later it had increased to \(420\). To model these data the year 1985 was designated as year zero. The increase in deer population from year \(n - 1\) to year \(n\) is three times the increase from year \(n - 2\) to year \(n - 1\). The deer population in year \(n\)<em> </em>is denoted by \({x_n}\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show that for \(n \geqslant 2,{\text{ }}{x_n} = 4{x_{n - 1}} - 3{x_{n - 2}}\).</p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Solve the recurrence relation.</p>
<div class="marks">[6]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Show using proof by strong induction that the solution is correct.</p>
<div class="marks">[9]</div>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">\({x_n} - {x_{n - 1}} = 3({x_{n - 1}} - {x_{n - 2}})\) <span class="Apple-converted-space"> </span><strong><em>M1A2</em></strong></p>
<p class="p1">\({x_n} = 4{x_{n - 1}} - 3{x_{n - 2}}\) <span class="Apple-converted-space"> </span><strong><em>AG</em></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">we need to solve the quadratic equation \({t^2} - 4t + 3 = 0\) <span class="Apple-converted-space"> </span><strong><em>(M1)</em></strong></p>
<p class="p1">\(t = 3,{\text{ }}1\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">\({x_n} = a \times {1^n} + b \times {3^n}\)</p>
<p class="p1">\({x_n} = a + b \times {3^n}\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">\(330 = a + b\) <span class="s1">and<span class="Apple-converted-space"> </span></span>\(420 = a + 3b\) <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1">\(a = 285\) <span class="s1">and </span>\(b = 45\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">\({x_n} = 285 + 45 \times {3^n}\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">\({x_n} = 4{x_{n - 1}} - 3{x_{n - 2}}\)</p>
<p class="p1">\({x_n} = 285 + 45 \times {3^n}\)</p>
<p class="p1">let \(n = 0 \Rightarrow {x_0} = 330\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">let \(n = 1 \Rightarrow {x_1} = 420\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">hence true for \(n = 0,{\text{ }}n = 1\)</p>
<p class="p1">assume true for \(n = k,{\text{ }}{x_k} = 285 + 45 \times {3^k}\) <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1">and assume true for \(n = k - 1,{\text{ }}{x_{k - 1}} = 285 + 45 \times {3^{k - 1}}\) <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1">consider \(n = k + 1\)</p>
<p class="p1">\({x_{k + 1}} = 4{x_k} - 3{x_{k - 1}}\) <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1">\({x_{k + 1}} = 4(285 + 45 \times {3^k}) - 3(285 + 45 \times {3^{k - 1}})\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">\({x_{k + 1}} = 4(285) - 3(285) + 4(45 \times {3^k}) - (45 \times {3^k})\) <span class="Apple-converted-space"> </span><strong><em>(A1)</em></strong></p>
<p class="p1">\({x_{k + 1}} = 285 + 3(45 \times {3^k})\)</p>
<p class="p1">\({x_{k + 1}} = 285 + 45 \times {3^{k + 1}}\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">hence if solution is true for \(k\) and \(k - 1\) it is true for. However solution is true for \(k = 0\), \(k = 1\). Hence true for all \(k\). Hence proved by the principle of strong induction <span class="Apple-converted-space"> </span><strong><em>R1</em></strong></p>
<p class="p2"> </p>
<p class="p1"><strong>Note: </strong>Do not award final reasoning mark unless candidate has been awarded at least 4 other marks in this part.</p>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">Students often gained full marks on parts a) and b), but a minority of candidates made no start to the question at all.</p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">Students often gained full marks on parts a) and b), but a minority of candidates made no start to the question at all.</p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">In part c) it was pleasing to see a number of fully correct solutions to the strong induction, but many candidates lost marks for not being fully rigorous in the proof.</p>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph </span><span style="font-family: times new roman,times; font-size: medium;">shown below. State the weight of the tree.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><br><img src="images/kruskal_1.png" alt></span></p>
<div class="marks">[5]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">For the travelling salesman problem defined by this graph, find</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) an upper bound;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) a lower bound.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given that the integers \(m\) and \(n\) are such that \(3|({m^2} + {n^2})\) , prove that \(3|m\) </span><span style="font-family: times new roman,times; font-size: medium;">and \(3|n\) .</span></p>
<div class="marks">[7]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Hence</strong> show that \(\sqrt 2 \) is irrational.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">B.b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="color: #000000; font-family: Times New Roman; font-size: medium;"> <img src="images/kruskal.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">Start at an edge with weight \(2\), say BH, add other edges of weight \(2\) such that a cycle is not formed. Continue to add edges of increasing weight until all vertices have been included. <strong><em>M1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">thus the minimum spanning tree is </span></p>
<p><span style="font-family: Times New Roman; font-size: medium;">\({\rm{BH + HC + GK + KH + KE + EF + GA + CD}}\) </span><strong><em><span style="font-family: times new roman,times; font-size: medium;">A3 </span></em></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;">total weight \( = 2 + 2 + 3 + 4 + 4 + 4 + 5 + 5 = 29\) <strong><em>A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: GB may replace KH and other orders are possible. </span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> [5 marks] </span></em></strong></p>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-size: medium;"><span style="font-family: times new roman,times;">(i) upper bound \( = 2 \times \) weight of minimum spanning tree <strong><em>M1</em></strong></span></span></p>
<p style="margin-left: 30px;"><span style="font-family: Times New Roman; font-size: medium;">\( = 58\) </span><strong><em><span style="font-family: times new roman,times; font-size: medium;">A1 </span></em></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) deleting vertex F <em><strong> M1</strong> </em></span></p>
<p><br><img src="images/tulsa.png" alt></p>
<p><span style="font-family: times new roman,times; font-size: medium;">the minimum spanning tree is </span></p>
<p><span style="font-family: Times New Roman; font-size: medium;">\({\rm{BH + HC + GK + KE + KH + GA + CD}}\) </span><strong><span style="font-family: times new roman,times; font-size: medium;"><em>A2</em> </span></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;">total weight \( = 2 + 2 + 3 + 4 + 4 + 5 + 5 = 25\) <strong><em>A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">adding the two edges of least weight from F <em><strong>M1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">lower bound \( = 25 + 4 + 6 = 35\) <strong><em>A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Alternative solutions may be given by deleting a different vertex.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> [8 marks]</span></em></strong></p>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;"><strong>EITHER</strong> </span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\(3|m \Rightarrow m \equiv 0(\bmod 3)\) <strong><em>(R1)</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">if this is false then \(m \equiv 1\) or \(2(\bmod 3)\) and \({m^2} \equiv 1\) or \(4(\bmod 3)\) <strong><em>R1A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">since \(4 \equiv 1(\bmod 3)\) then \({m^2} \equiv 1(\bmod 3)\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">similarly \({n^2} \equiv 1(\bmod 3)\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">hence \({m^2} + {n^2} \equiv 2(\bmod 3)\)</span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">but \({m^2} + {n^2} \equiv 0(\bmod 3)\) <strong><em>(R1)</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">this is a contradiction so \(3|m\) and \(3|n\) <strong><em>R1AG </em></strong></span></p>
<p align="JUSTIFY"><strong><span style="font-family: times new roman,times; font-size: medium;">OR </span></strong></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\(m \equiv 0\) , 1 or \(2(\bmod 3)\) and \(n \equiv 0\) , 1 or \(2(\bmod 3)\) <em><strong>M1R1</strong> </em></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow {m^2} \equiv 0\) or \(1(\bmod 3)\) and \({n^2} \equiv 0\) or \(1(\bmod 3)\) <strong><em>A1A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">so \({m^2} + {n^2} \equiv 0,1,2(\bmod 3)\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">but \(3|{m^2} + {n^2}\) so \({m^2} + {n^2} \equiv 0(\bmod 3)\) <em><strong>R1</strong> </em></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\(m \equiv 0(\bmod 3)\) and \(n \equiv 0(\bmod 3)\) <strong><em> R1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow 3|m\) and \(3|n\) <strong><em>AG </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[7 marks] </span></em></strong></p>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">suppose \(\sqrt 2 = \frac{a}{b}\) , where \(a,b \in \mathbb{Z}\) and \(a\) and \(b\) are coprime <strong><em> M1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">then </span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\(2{b^2} = {a^2}\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\({a^2} + {b^2} = 3{b^2}\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\(3{b^2} \equiv 0(\bmod 3)\) <strong><em>A1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">but by (a) \(a\) and \(b\) have a common factor so \(\sqrt 2 \ne \frac{a}{b}\) <strong><em>R1</em> </strong></span></p>
<p align="JUSTIFY"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow \sqrt 2 \) is irrational <strong><em>AG </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[5 marks] </span></em></strong></p>
<div class="question_part_label">B.b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This was usually well done although some candidates have difficulty showing clearly the procedure through the algorithm. </span></p>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This was usually well done although some candidates have difficulty showing clearly the procedure through the algorithm. </span></p>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Part (a) was not well done although there were many suspect attempts at a proof. </span></p>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">If part (a) was missed it should still have been possible to use the "Hence" to complete part (b). Unfortunately this did not often happen. </span></p>
<div class="question_part_label">B.b.</div>
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(a) Consider the recurrence relation \(a{u_{n + 1}} + b{u_n} + c{u_{n - 1}} = 0\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">Show that \({u_n} = A{\lambda ^n} + B{\mu ^n}\) satisfies this relation where \(A\), \(B\) are arbitrary constants and \(\lambda \), \(\mu \) are the roots of the equation \(a{x^2} + bx + c = 0\).</span></p>
<p style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 21px; line-height: normal; font-family: Helvetica; margin: 0px; text-align: center;"><span style="font-family: 'times new roman', times; font-size: medium;">(b) <br><img src="images/Schermafbeelding_2014-09-19_om_14.22.07.png" alt></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">A particle \(P\) executes a random walk on the line above such that when it is at point \(n\left( {1 \leqslant n \leqslant 9,{\text{ }}n \in {\mathbb{Z}^ + }} \right)\) it has a probability \(0.4\) of moving to \(n + 1\) and a probability \(0.6\) of moving to \(n - 1\). The walk terminates as soon as \(P\) reaches either \(0\) or \(10\). Let \({p_n}\) denote the probability that the walk terminates at \(0\) starting from \(n\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) Show that \(2{p_{n + 1}} - 5{p_n} + 3{p_{n - 1}} = 0\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) By solving this recurrence relation subject to the boundary conditions \({p_0} = 1\), \({p_{10}} = 0\) show that \({p_n} = \frac{{{{1.5}^{10}} - {{1.5}^n}}}{{{{1.5}^{10}} - 1}}\).</span></p>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(a) consider</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(a{u_{n + 1}} + b{u_n} + c{u_{n - 1}} = aA{\lambda ^{n + 1}} + aB{\mu ^{n + 1}} + bA{\lambda ^n} + bB{\mu ^n} + cA{\lambda ^{n - 1}} + cB{\mu ^{n - 1}}\) <strong><em>M1A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\( = A{\lambda ^{n - 1}}\left( {a{\lambda ^2} + b\lambda + c} \right) + B{\mu ^{n - 1}}\left( {a{\mu ^2} + b\mu + c} \right)\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(= 0 \)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em>[3 marks]</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em> </em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(b) (i) to terminate at \(0\) starting from \(n\), the particle must either move to \(n + 1\) and terminate at \(0\) starting from there or move to \(n - 1\) and terminate at \(0\) starting from there</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">therefore,</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\({p_n} = 0.4{p_{n + 1}} + 0.6{p_{n - 1}}\) <strong><em>M1A2</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">leading to \(2{p_{n + 1}} - 5{p_n} + 3{p_{n - 1}} = 0\) <strong><em>AG</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) solving the auxiliary equation \(2{x^2} - 5x + 3 = 0\) <strong><em>M1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(x = 1,{\text{ 1.5}}\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">the general solution is</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\({p_n} = A + B{(1.5)^n}\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">substituting the boundary conditions,</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(A + B = 1\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(A + B{(1.5)^{10}} = 0\) <strong><em>M1A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">solving,</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\(A = \frac{{{{1.5}^{10}}}}{{{{1.5}^{10}} - 1}};{\text{ }}B = - \frac{1}{{{{1.5}^{10}} - 1}}\) <strong><em>A1A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">giving</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\({p_n} = \frac{{{{1.5}^{10}} - {{1.5}^n}}}{{{{1.5}^{10}} - 1}}\) <strong><em>AG</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em>[10 marks]</em></strong></span></p>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question">
[N/A]
</div>
<br><hr><br><div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">The vertices and weights of the graph \(G\) are given in the following table.</span></p>
<p style="font: normal normal normal 21px/normal 'Times New Roman'; text-align: center; margin: 0px;"><br><span style="font-family: 'times new roman', times; font-size: medium;"><img src="images/Schermafbeelding_2014-09-19_om_14.03.12.png" alt></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree for \(G\), indicating clearly the order in which the edges are included.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Draw the minimum spanning tree for \(G\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(b) Consider the travelling salesman problem for \(G\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) An upper bound for the problem can be found by doubling the weight of the minimum spanning tree. Use this method to find an upper bound.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Starting at \({\text{A}}\), use the nearest neighbour algorithm to find another upper bound.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(iii) By first removing \({\text{A}}\), use the deleted vertex algorithm to find a lower bound for the problem.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(c) The travelling salesman problem is now modified so that starting at \({\text{A}}\), the vertices \({\text{B}}\) and \({\text{C}}\) have to be visited first in that order, then \({\text{D}}\), \({\text{E}}\), \({\text{F}}\) in any order before returning to \({\text{A}}\).</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(i) Solve this modified problem.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) Comment whether or not your answer has any effect on the upper bound to the problem considered in (b).</span></p>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question">
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(a) (i) using Kruskal’s algorithm, the minimum spanning tree is built up as follows</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"><span style="background-color: #f7f7f7;">\({\text{BF}}\)</span> <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{BE, BC}}\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{DE, AD}}\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) <br><img src="images/A_to_F.jpg" alt> <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em>[4 marks]</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px Helvetica;"><span style="font-family: 'times new roman', times; font-size: medium;">(b) (i) weight of minimum spanning tree \(= 69\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;"><strong>Note: </strong>This mark may be earned earlier.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">upper bound \(= 138\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) starting at \({\text{A}}\), the cycle is \({\text{A}} \to {\text{D}} \to {\text{E}} \to {\text{B}} \to {\text{F}} \to {\text{C}} \to {\text{A}}\) <strong><em>M1A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">an upper bound is the total weight of this cycle <strong><em>(M1)</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\(17 + 16 + 12 + 10 + 20 + 19 = 94\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(iii) the minimum spanning tree of the reduced graph is as above with AD removed <strong><em>(R1)</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">its total weight is \(10 + 12 + 14 + 16 = 52\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">adding the weights of the two deleted edges of the minimum spanning tree gives <strong><em>(M1)</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">lower bound \( = 52 + 17 + 18 = 87\) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em>[10 marks]</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em> </em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(c) (i) the possible cycles, and their weights, are</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{F}} \to {\text{A Weight 102 (or 70 exc A}} \to {\text{B}} \to {\text{C)}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{F}} \to {\text{E}} \to {\text{A Weight 107 (or 75 exc A}} \to {\text{B}} \to {\text{C)}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{D}} \to {\text{F}} \to {\text{A Weight 106 (or 74 exc A}} \to {\text{B}} \to {\text{C)}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{F}} \to {\text{D}} \to {\text{A Weight 99 (or 67 exc A}} \to {\text{B}} \to {\text{C)}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{D}} \to {\text{E}} \to {\text{A Weight 110 (or 78 exc A}} \to {\text{B}} \to {\text{C)}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A Weight 98 (or 66 exc A}} \to {\text{B}} \to {\text{C)}}\) <strong><em>A3</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;"><strong>Note: </strong>Award <strong><em>A(3 – n) </em></strong>for \(n\) errors up to \(n = 2\), <strong><em>A0 </em></strong>thereafter.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman'; min-height: 25.0px;"> </p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">the solution is therefore the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A}}\)</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(with weight \(98\)) <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;">(ii) no, it has no effect <strong><em>A1</em></strong></span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 21.0px 'Times New Roman';"><span style="font-family: 'times new roman', times; font-size: medium;"><strong><em>[5 marks]</em></strong></span></p>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question">
[N/A]
</div>
<br><hr><br><div class="specification">
<p class="p1"><span class="s1">The sequence \(\{ {u_n}:n \in {\mathbb{Z}^ + }\} \) </span>satisfies the recurrence relation \(2{u_{n + 2}} - 3{u_{n + 1}} + {u_n} = 0\), where \({u_1} = 1,{\text{ }}{u_2} = 2\).</p>
</div>
<div class="specification">
<p class="p1">The sequence \(\{ {w_n}:n \in \mathbb{N}\} \) satisfies the recurrence relation \({w_{n + 2}} - 2{w_{n + 1}} + 4{w_n} = 0\), where \({w_0} = 0,{\text{ }}{w_1} = 2\).</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>Find an expression for \({u_n}\) in terms of \(n\).</p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>Show that the sequence converges, stating the limiting value.</p>
<div class="marks">[9]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1"><span class="s1">The sequence </span>\(\{ {v_n}:n \in {\mathbb{Z}^ + }\} \) satisfies the recurrence relation \(2{v_{n + 2}} - 3{v_{n + 1}} + {v_n} = 1\), where \({v_1} = 1,{\text{ }}{v_2} = 2\)<span class="s2">.</span></p>
<p class="p1">Without solving the recurrence relation prove that the sequence diverges.</p>
<div class="marks">[3]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>Find an expression for \({w_n}\) in terms of \(n\).</p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>Show that \({w_{3n}} = 0\) for all \(n \in \mathbb{N}\).</p>
<div class="marks">[7]</div>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>the auxiliary equation is \(2{r^2} - 3r + 1 = 0\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>(M1)</em></strong></span></p>
<p class="p1">with roots \(r = 1,{\text{ }}\frac{1}{2}\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p2">the general solution of the difference equation is <span class="Apple-converted-space"> </span><strong><em>(M1)</em></strong></p>
<p class="p3"><span class="Apple-converted-space">\({u_n} = A + B{\left( {\frac{1}{2}} \right)^n}\) </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p2">imposing the initial conditions <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1"><span class="Apple-converted-space">\(A + \frac{B}{2} = 1,{\text{ }}A + \frac{B}{4} = 2\) </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p2">obtain \({u_n} = 3 - 4{\left( {\frac{1}{2}} \right)^n}\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">(ii) <span class="Apple-converted-space"> </span>as \(n \to \infty ,{\text{ }}{\left( {\frac{1}{2}} \right)^n} \to 0\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>R1</em></strong></span></p>
<p class="p1"><span class="Apple-converted-space">\({u_n} \to 3\) </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p2">hence the sequence is convergent <span class="Apple-converted-space"> </span><strong><em>AG</em></strong></p>
<p class="p2"><strong><em>[9 marks]</em></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">assume \({v_n} \to L\) <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p1">taking the limit of both sides of the recurrence relation <span class="Apple-converted-space"> </span><strong><em>M1</em></strong></p>
<p class="p2">\(2L - 3L + L{\text{ }}( = 0) = 1\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p1">the contradiction shows that the sequence diverges <span class="Apple-converted-space"> </span><strong><em>AG</em></strong></p>
<p class="p1"><strong><em>[3 marks]</em></strong></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">(i) <span class="Apple-converted-space"> </span>the auxiliary equation \({r^2} - 2r + 4 = 0\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">has roots \(1 \pm {\text{i}}\sqrt 3 \) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1"><strong>METHOD 1</strong></p>
<p class="p2">these can be re-expressed as \(2\left( {\cos \left( {\frac{\pi }{3}} \right) \pm {\text{i}}\sin \left( {\frac{\pi }{3}} \right)} \right)\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>M1</em></strong></span></p>
<p class="p2">the general solution is</p>
<p class="p2"><span class="Apple-converted-space">\({w_n} = {2^n}\left( {A\cos \left( {\frac{{n\pi }}{3}} \right) + B\sin \left( {\frac{{n\pi }}{3}} \right)} \right)\) </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p1">imposing the initial conditions</p>
<p class="p1"><span class="Apple-converted-space">\(A = 0,{\text{ }}2B\frac{{\sqrt 3 }}{2} = 2\) </span><strong><em>A1</em></strong></p>
<p class="p1">obtain \({w_n} = \frac{{{2^{n + 1}}}}{{\sqrt 3 }}\sin \left( {\frac{{n\pi }}{3}} \right)\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1"><strong>METHOD 2</strong></p>
<p class="p3">the general solution is</p>
<p class="p3">\({w_n} = A{\left( {1 + {\text{i}}\sqrt 3 } \right)^n} + B{\left( {1 - {\text{i}}\sqrt 3 } \right)^n}\) <strong><em>A1</em></strong></p>
<p class="p3">imposing the initial conditions</p>
<p class="p3"><span class="Apple-converted-space">\(A + B = 0,{\text{ }}A + B + {\text{i}}\sqrt 3 (A - B) = 2\) </span><strong><em>M1A1</em></strong></p>
<p class="p3">obtain \({w_n} = \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 + {\text{i}}\sqrt 3 } \right)^n} - \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 - {\text{i}}\sqrt 3 } \right)^n}\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p3"> </p>
<p class="p3">(ii) <span class="Apple-converted-space"> </span><strong>METHOD 1</strong></p>
<p class="p6"><span class="Apple-converted-space">\({w_{3n}} = \frac{{{2^{3n + 1}}}}{{\sqrt 3 }}\sin (n\pi )\) </span><span class="s6"><strong><em>R1</em></strong></span></p>
<p class="p6"><span class="Apple-converted-space">\( = 0\) </span><span class="s6"><strong><em>AG</em></strong></span></p>
<p class="p3"><strong>METHOD 2</strong></p>
<p class="p4">\({w_{3n}} = \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 + {\text{i}}\sqrt 3 } \right)^{3n}} - \frac{1}{{{\text{i}}\sqrt 3 }}{\left( {1 - {\text{i}}\sqrt 3 } \right)^{3n}}\)</p>
<p class="p4"><span class="Apple-converted-space">\( = \frac{1}{{{\text{i}}\sqrt 3 }}{( - 8)^n} - \frac{1}{{{\text{i}}\sqrt 3 }}{( - 8)^n}\) </span><span class="s6"><strong><em>R1</em></strong></span></p>
<p class="p6"><span class="Apple-converted-space">\( = 0\) </span><span class="s6"><strong><em>AG</em></strong></span></p>
<p class="p3"><strong><em>[7 marks]</em></strong></p>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">A significant number of candidates had clearly not learned the mechanical procedure for solving linear three-term recurrences. Those who were well prepared, coped well with parts (a) and (c). Part (b) was very rarely successfully answered. Some candidates proved that \({v_{n + 1}} > {v_n}\) but erroneously concluded that the sequence diverged.</p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>A significant number of candidates had clearly not learned the mechanical procedure for solving linear three-term recurrences. Those who were well prepared, coped well with parts (a) and (c). Part (b) was very rarely successfully answered. Some candidates proved that \({v_{n + 1}} > {v_n}\) but erroneously concluded that the sequence diverged.</p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>A significant number of candidates had clearly not learned the mechanical procedure for solving linear three-term recurrences. Those who were well prepared, coped well with parts (a) and (c). Part (b) was very rarely successfully answered. Some candidates proved that \({v_{n + 1}} > {v_n}\) but erroneously concluded that the sequence diverged.</p>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A canal system divides a city into six land masses connected by fifteen bridges, </span><span style="font-family: times new roman,times; font-size: medium;">as shown in the diagram below.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/canals.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Draw a planar graph to represent this map.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Write down the adjacency matrix of the graph.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">List the degrees of each of the vertices.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">State with reasons whether or not this graph has</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) an Eulerian circuit;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (ii) an Eulerian trail.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Find the number of walks of length \(4\) from E to F.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><img src="images/ams.png" alt></span><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A2</span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></strong></em></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><img src="images/matrix.png" alt></span><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A2</span></strong></em></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Award <em><strong>A1</strong></em> for one error or omission, <em><strong>A0</strong></em> for more than one error or </span><span style="font-family: times new roman,times; font-size: medium;">omission. Two symmetrical errors count as one error.</span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></strong></em></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> A B C D E F</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(8, 4, 4, 3, 5, 6) <em><strong>A2</strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></strong></em></p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) no, because there are odd vertices <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) yes, because there are exactly two odd vertices <strong><em>M1A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[4 marks]</span></em></strong></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><img src="images/adj.png" alt></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">number of walks of length \(4\) is \(170\) <em><strong>(M1)A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: The complete matrix need not be shown. Only one of the FE has </span><span style="font-family: times new roman,times; font-size: medium;">to be shown.</span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></strong></em></p>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Parts (a) to (c) and (e) did not prove unusually difficult and were answered well. </span></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Parts (a) to (c) and (e) did not prove unusually difficult and were answered well. </span></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Parts (a) to (c) and (e) did not prove unusually difficult and were answered well. </span></p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Part (d) proved more problematic since there was confusion between the conditions to be satisfied for there to be a circuit and a trail. There is a difference between "there are two odd vertices" and "there are exactly two odd vertices". As noted elsewhere on paper 1, appreciation of the restrictions as well as the applications of results in mathematics should both be emphasized. </span></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Parts (a) to (c) and (e) did not prove unusually difficult and were answered well. N</span><span style="font-family: times new roman,times; font-size: medium;">ot all of the matrix in part (e) needed to be shown. </span></p>
<div class="question_part_label">e.</div>
</div>
<br><hr><br><div class="specification">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A group of people: Andrew, Betty, Chloe, David, Edward, Frank and Grace, has certain </span><span style="font-family: times new roman,times; font-size: medium;">mutual friendships:</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Andrew is friendly with Betty, Chloe, David and Edward;</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Frank is friendly with Betty and Grace;</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">David, Chloe and Edward are friendly with one another.</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Draw the planar graph \(H\) that represents these mutual friendships.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) State how many faces this graph has.</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Determine, giving reasons, whether \(H\) has</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (i) a Hamiltonian path;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (ii) a Hamiltonian cycle;</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> (iii) an Eulerian circuit;</span></p>
<p style="margin-left: 30px;"><span style="font-family: times new roman,times; font-size: medium;"> (iv) an Eulerian trail.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Verify Euler’s formula for \(H\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">State, giving a reason, whether or not \(H\) is bipartite.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Write down the adjacency matrix for \(H\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">David wishes to send a message to Grace, in a sealed envelope, through mutual friends.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">In how many different ways can this be achieved if the envelope is passed seven </span><span style="font-family: times new roman,times; font-size: medium;">times and Grace only receives it once?</span></p>
<div class="marks">[7]</div>
<div class="question_part_label">f.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(i)<br><img src="images/pink.png" alt></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A2 </span></strong></em></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Award <em><strong>A1</strong></em> if one error made. </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) \(4\) <strong><em>A1 </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[3 marks] </span></em></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(i) yes, for example GFBACDE <em><strong>A1R1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) no, for example F and B would be visited twice <strong><em>A1R1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(iii) no, because the graph contains vertices of odd degree <strong><em>A1R1 </em></strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(iv) no, because there are more than two vertices of odd degree <strong><em>A1R1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: The <em><strong>A</strong></em> and<strong><em> R</em></strong> marks can be considered as independent. </span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[8 marks] </span></em></strong></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">\(v = 7\) , \(e = 9\) <strong><em>A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">\(f = 4\) from (a)(ii) </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">\(9 + 2 = 7 + 4\) <em><strong>R1AG </strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks] </span></strong></em></p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">no, because the graph contains at least one triangle <strong><em>A1R1 </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[2 marks] </span></em></strong></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">\(\left( {\begin{array}{*{20}{c}}<br> {}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}}&{\text{F}}&{\text{G}} \\ <br> {\text{A}}&0&1&1&1&1&0&0 \\ <br> {\text{B}}&1&0&0&0&0&1&0 \\ <br> {\text{C}}&1&0&0&1&1&0&0 \\ <br> {\text{D}}&1&0&1&0&1&0&0 \\ <br> {\text{E}}&1&0&1&1&0&0&0 \\ <br> {\text{F}}&0&1&0&0&0&0&1 \\ <br> {\text{G}}&0&0&0&0&0&1&0 <br>\end{array}} \right)\)</span> <em><strong><span style="font-family: times new roman,times; font-size: medium;">A2 </span></strong></em></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: <em><strong>A1</strong></em> for one error, <em><strong>A0</strong></em> for more than one error. </span></p>
<p><strong><em> <span style="font-family: times new roman,times; font-size: medium;">[2 marks] </span></em></strong></p>
<div class="question_part_label">e.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>METHOD 1</strong> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">DG element of 7<sup>th</sup> power of matrix \( = 26\) <em><strong>M1A1A1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: <em><strong>M1</strong></em> for attempt at some power; <em><strong>A1</strong></em> for 7<sup>th</sup> power; <em><strong>A1</strong></em> for \(26\).</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">DG element of the 5<sup>th</sup> power of the matrix \( = 2\) <strong><em>A1A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">obtain \(26 - 2 = 24\) <strong><em>M1A1 </em></strong></span></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;"> </span></strong></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;">METHOD 2</span></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;">the observation that letter has to reach Grace after Frank obtains it after \(6\) passings, (without Grace having received it earlier) <em><strong>(M1)(A1)</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">statement that the G row and column have been deleted <strong><em>A1A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">DF element of 6<sup>th</sup> power of new matrix is \(24\) <strong><em>M1A1A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: <em><strong>M1</strong></em> for attempt at some power of new or old matrix; <strong><em>A1</em></strong> for 6<sup>th</sup> </span><span style="font-family: times new roman,times; font-size: medium;">power of new matrix; <strong><em>A1</em></strong> for 24. </span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[7 marks] </span></em></strong></p>
<div class="question_part_label">f.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done.</span></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done. Candidates who lost marks tended to do so as follows: (b)(i) for failing to give an example of a Hamiltonian path; (b)(ii) for giving an incomplete reason for the non-existence of a Hamiltonian cycle; (b)(iii)(iv) for giving the same reason for both parts.</span></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done.</span></p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done. Candidates who lost marks tended to do so as follows: (d) for giving the definition of a bipartite graph as the reason for the fact that \(H\) is not bipartite.</span></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done.</span></p>
<div class="question_part_label">e.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was generally well done.</span></p>
<div class="question_part_label">f.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(G\) has the following cost adjacency matrix.<br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/finn.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">Draw \(G\) in planar form.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given that \(ax \equiv b(\bmod p)\) where \(a,b,p,x \in {\mathbb{Z}^ + }\) , \(p\) is prime and \(a\) is not a </span><span style="font-family: times new roman,times; font-size: medium;">multiple of \(p\), use Fermat’s little theorem to show that</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(x \equiv {a^{p - 2}}b(\bmod p)\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Hence solve the simultaneous linear congruences\[3x \equiv 4(\bmod 5)\]\[5x \equiv 6(\bmod 7)\]giving your answer in the form \(x \equiv c(\bmod d)\) .</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">B.b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><img src="images/dkny.png" alt></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A2</span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></strong></em></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: The weights are not required for this <strong><em>A2</em></strong>.</span></p>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Multiply through by \({a^{p - 2}}\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\({a^{p - 1}}x \equiv {a^{p - 2}}b(\bmod p)\) <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Since, by Fermat’s little theorem, \({a^{p - 1}} \equiv 1(\bmod p)\) , <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(x \equiv {a^{p - 2}}b(\bmod p)\) <strong><em>AG</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[3 marks]</span></em></strong></p>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Using the result from (a),</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(x \equiv {3^3} \times 4(\bmod 5) \equiv 3(\bmod 5)\) <strong><em> M1A1</em></strong></span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( = 3\), \(8\), \(13\), \(18\), \(23\),… <strong><em>(A1)</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">and \(x \equiv {5^5} \times 6(\bmod 7) \equiv 4(\bmod 7)\) <em><strong>M1A1</strong></em></span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( = 4\), \(11\), \(18\), \(25\),… <em><strong> (A1)</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">The general solution is</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(x = 18 + 35n\) <em><strong>M1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><em>i.e.</em> \(x \equiv 18(\bmod 35)\) <strong><em>A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[8 marks]</span></em></strong></p>
<div class="question_part_label">B.b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">B.b.</div>
</div>
<br><hr><br><div class="specification">
<p><img src="images/watch.png" alt></p>
<p><span style="font-family: times new roman,times; font-size: medium;">The diagram above shows the graph \(G\).</span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain briefly why \(G\) has no Eulerian circuit.</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Determine whether or not \(G\) is bipartite.</span></p>
<p style="margin-left: 30px;" align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(iii) Write down the adjacency matrix of <strong><em>G</em></strong>. Hence find the number of walks of </span><span style="font-family: times new roman,times; font-size: medium;">length \(4\) beginning at A and ending at C.</span></p>
<div class="marks">[12]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The cost adjacency matrix of a graph with vertices P, Q, R, S, T, U is given by</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/14k.png" alt></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Dijkstra’s Algorithm to find the length of the shortest path between the </span><span style="font-family: times new roman,times; font-size: medium;">vertices P and S. Show all the steps used by the algorithm and list the order of </span><span style="font-family: times new roman,times; font-size: medium;">the vertices in the path.</span></p>
<div class="marks">[12]</div>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(i) Because the graph has vertices of odd degree. <strong><em>R2</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) We are looking for \(2\) disjoint sets. <strong><em>(M1)</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">Put A in Set 1. Then B and D have to go in Set 2. This means that E and C have to go in Set 1. Therefore the disjoint sets are \(\left\{ {{\rm{B,D}}} \right\}\) and \(\left\{ {{\rm{A,C,E}}} \right\}\) . All the edges join a vertex from one set to a vertex in the other set. <strong><em>R2</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">The graph is bipartite. <strong><em>A1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(iii)<br></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">\({\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}}<br> 0&2&0&1&0 \\ <br> 2&0&1&0&2 \\ <br> 0&1&0&1&0 \\ <br> 1&0&1&0&1 \\ <br> 0&2&0&1&0 <br>\end{array}} \right)\)<br></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">We require the (\(1\), \(3\)) or (\(3\), \(1\)) element of \({\boldsymbol{M}^4}\) . <em><strong>M1M1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">Using a GDC, the number of walks of length \(4\) is \(36\). <strong><em>A2 </em></strong></span></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;"><em> </em></span></strong></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;"><em>[12 marks]</em> </span></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><img src="images/16k.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">The length of the shortest path is \(18\). <strong><em>A2</em> </strong></span></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;">EITHER </span></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;">P U Q T R S <strong><em>A2</em> </strong></span></p>
<p><strong><span style="font-family: times new roman,times; font-size: medium;">OR </span></strong></p>
<p><span style="font-family: times new roman,times; font-size: medium;">P U Q T S <strong><em>A2</em> </strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[12 marks] </span></em></strong></p>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Given the linear congruence \(ax \equiv b({\rm{mod}}p)\) , where \(a\) , \(b \in \mathbb{Z} \) , \(p\) is a prime and </span><span style="font-family: times new roman,times; font-size: medium;">\({\rm{gcd}}(a,p) = 1\) , show that \(x \equiv {a^{p - 2}}b({\rm{mod}}p)\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Solve \(17x \equiv 14(\bmod 21)\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Use the solution found in part (i) to find the general solution to the </span><span style="font-family: times new roman,times; font-size: medium;">Diophantine equation \(17x + 21y = 14\) .</span></p>
<div class="marks">[10]</div>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(ax \equiv b({\rm{mod}}p)\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow {a^{p - 2}} \times ax \equiv {a^{p - 2}} \times b({\rm{mod}}p)\) <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow {a^{p - 1}}x \equiv {a^{p - 2}} \times b({\rm{mod}}p)\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">but \({a^{p - 1}} \equiv 1({\rm{mod}}p)\) by Fermat’s little theorem <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow x \equiv {a^{p - 2}} \times b({\rm{mod}}p)\) <strong><em>AG</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Award <em><strong>M1</strong></em> for some correct method and <em><strong>A1</strong></em> for correct statement.</span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[4 marks]</span></strong></em></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) \(17x \equiv 14(\bmod 21)\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow x \equiv {17^{19}} \times 14(\bmod 21)\) <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\({17^6} \equiv 1(\bmod21)\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow x \equiv {(1)^3} \times 17 \times 14(\bmod 21)\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow x \equiv 7(\bmod21)\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong><em> </em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) \(x \equiv 7(mod21)\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow x = 7 + 21t\) , \(t \in \mathbb{Z}\) <em><strong>M1A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow 17(7 + 21t) + 21y = 14\) <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow 119 + 357t + 21y = 14\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow 21y = - 105 - 357t\) <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\( \Rightarrow y = - 5 - 17t\) <em><strong>A1</strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> </span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[10 marks]</span></strong></em></p>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Some creative ways of doing this part involved more work than four marks merited although there were many solutions that were less simple than that in the markscheme. </span></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(b)(i) Various ways were used and accepted. </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Alternative valid solutions were found and in general this part was found to be within the reach of most candidates. </span></p>
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The following diagram shows a weighted graph \(G\) .</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img style="display: block; margin-left: auto; margin-right: auto;" src="images/andre.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain briefly what features of the graph enable you to state that \(G\) has </span><span style="font-family: times new roman,times; font-size: medium;">an Eulerian trail but does not have an Eulerian circuit.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Write down an Eulerian trail in \(G\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Use Kruskal’s algorithm to find and draw the minimum spanning tree for \(G\) . </span><span style="font-family: times new roman,times; font-size: medium;">Your solution should indicate the order in which the edges are added.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) State the weight of the minimum spanning tree.</span></p>
<div class="marks">[5]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Use Dijkstra’s algorithm to find the path of minimum total weight joining </span><span style="font-family: times new roman,times; font-size: medium;">A to D, and state its weight. Your solution should indicate clearly the use of </span><span style="font-family: times new roman,times; font-size: medium;">this algorithm.</span></p>
<div class="marks">[10]</div>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(i) \(G\) has an Eulerian trail because it has \(2\) vertices of odd degree and the remaining vertices of even degree <strong><em>R1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">\(G\) does not have an Eulerian circuit because not all vertices are of even degree <strong><em>R1</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) BAFBCFECDE <strong><em>A1 </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[3 marks] </span></em></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">(i) the edges are added in the order </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">FE <em><strong>A1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">CE </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">AB <em><strong>A1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">BF, CD </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">or CD, BF <em><strong>A1</strong> </em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><br><img src="images/lego.png" alt></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A1 </span></strong></em></p>
<p><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) minimum weight is \(19\) <em><strong>A1 </strong></em></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;"><em><strong> </strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[5 marks] </span></strong></em></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;"><img src="images/eternal.png" alt></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">the shortest path is AFCD <strong><em> A2</em> </strong></span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">the weight is \(16\) <strong><em>A1 </em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[10 marks] </span></em></strong></p>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in \(G\). Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor. </span></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in <strong><em>G</em></strong>. Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor. </span></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in \(G\). Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor. </span></p>
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(H\) has the following adjacency matrix.</span></p>
<p><br><span style="font-family: times new roman,times; font-size: medium;"><img style="display: block; margin-left: auto; margin-right: auto;" src="images/naomi.png" alt></span></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Show that \(H\) is bipartite.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Draw \(H\) as a planar graph.</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Explain what feature of \(H\) guarantees that it has an Eulerian circuit.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Write down an Eulerian circuit in \(H\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Find the number of different walks of length five joining A to B.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) Determine how many of these walks go through vertex F after passing </span><span style="font-family: times new roman,times; font-size: medium;">along two edges.</span></p>
<div class="marks">[6]</div>
<div class="question_part_label">A.c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">Find the maximum number of extra edges that can be added to \(H\) while keeping </span><span style="font-family: times new roman,times; font-size: medium;">it simple, planar and bipartite.</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">A.d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Find the smallest positive integer \(m\) such that \({3^m} \equiv 1(\bmod 22)\) .</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Given that \({3^{49}} \equiv n(\bmod 22)\) where \(0 \le n \le 21\) , find the value of \(n\) .</span></p>
<div class="marks">[4]</div>
<div class="question_part_label">B.b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Solve the equation \({3^x} \equiv 5(\bmod 22)\) .</span></p>
<div class="marks">[3]</div>
<div class="question_part_label">B.c.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) using any method, <strong><em>(M1)</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">find that \(\left\{ {{\rm{A,C,D,F}}} \right\}\) and \(\left\{ {{\rm{B,E,G}}} \right\}\) are disjoint sets of vertices <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">so that \(H\) is bipartite <em><strong>AG</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><br><img src="images/swan.png" alt></span><em><strong><span style="font-family: times new roman,times; font-size: medium;"> A1</span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> </span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[3 marks]</span></strong></em></p>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) all vertices are of even degree <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) DECBAGFBD <strong><em>A2</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[3 marks]</span></em></strong></p>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i)<br><img src="images/tempus.png" alt></span><strong><em><span style="font-family: times new roman,times; font-size: medium;"> M1</span></em></strong></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">number of walks \( = 36\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) recognition of the need to find walks of length \(2\) and walks of length \(3\) <strong><em>(M1)</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">number of walks of length \(2\) from A to F \( = 2\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">number of walks of length \(3\) from F to B \( = 6\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">required number of walks \( =12\) <strong><em>A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[6 marks]</span></em></strong></p>
<div class="question_part_label">A.c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">for a simple, bipartite graph to be planar,</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(e \le 2v - 4 = 10\) <strong><em>M1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">at the moment, \(e = 8\) which means that we cannot add more than \(2\) edges <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">we see that we can add \(2\) edges, <em>e.g.</em> EA and EF <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">the maximum number of edges we can add is therefore \(2\) <strong><em>A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[4 marks]</span></em></strong></p>
<div class="question_part_label">A.d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">evaluating successive powers of \(3\) <em><strong> (M1)</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\({3^1} \equiv 3(\bmod 22)\) , \({3^2} \equiv 9(\bmod 22)\) , \({3^3} \equiv 5(\bmod 22)\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\({3^4} \equiv 15(\bmod 22)\) , \({3^5} \equiv 1(\bmod 22)\) so \(m = 5\) <strong><em>A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[2 marks]</span></em></strong></p>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">since \({3^5} \equiv 1(\bmod 22)\) , \({3^{45}} = {({3^5})^9} \equiv 1(\bmod 22)\) <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">consider \({3^{49}} = {3^{45}} \times {3^4} \equiv 1 \times 15(\bmod 22)\) so \(n = 15\) <strong><em>M1A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[4 marks]</span></em></strong></p>
<div class="question_part_label">B.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">from (a), \(x = 3\) is a solution <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">since \({3^5} \equiv 1(\bmod 22)\) , the complete solution is \(x = 3 + 5N\) where \(N \in \bullet \) <strong><em>(M1)A1</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[3 marks]</span></em></strong></p>
<div class="question_part_label">B.c.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Solutions to (a) and (b) were generally satisfactory. </span></p>
<div class="question_part_label">A.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">Solutions to (a) and (b) were generally satisfactory. </span></p>
<div class="question_part_label">A.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">In (c)(ii), few candidates realised that they had to find the number of walks of length two joining A to F, the number of walks of length three joining F to B and then multiply these two numbers together. </span></p>
<div class="question_part_label">A.c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">In (d), most candidates noted that the number of edges, \(e\), was equal to \(8\) and that application of the inequality \(e \le 2v - 4\) gave \(e \le 10\) . They therefore concluded that two more edges could be drawn. It is, however, important to realise that the value of \(e\) given by this inequality is an upper bound that may not be attainable and that in this case, it was necessary to show that two extra edges could in fact be drawn. </span></p>
<div class="question_part_label">A.d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was well answered in general with a variety of methods seen. Most candidates realised that the numbers involved precluded the use of Fermat’s little theorem. </span></p>
<div class="question_part_label">B.a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">This question was well answered in general with a variety of methods seen. Most candidates realised that the numbers involved precluded the use of Fermat’s little theorem. </span></p>
<div class="question_part_label">B.b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">In (c), most candidates gave \(x = 3\) as a solution following their earlier work in (a) but many candidates failed to realise that their answer to (b) showed that the general solution to (c) was actually \(3 + 5N\) where \(N\) is a non negative integer. </span></p>
<div class="question_part_label">B.c.</div>
</div>
<br><hr><br><div class="specification">
<p style="text-align: center;"><img src="images/Schermafbeelding_2017-08-18_om_11.42.18.png" alt="M17/5/FURMA/HP2/ENG/TZ0/01"></p>
<p>The diagram shows the graph \(G\) with the weights of the edges marked.</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>State what features of the graph enable you to state that \(G\) contains an Eulerian trail but no Eulerian circuit.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down an Eulerian trail.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D, stating this total weight. Your solution should show clearly that this algorithm has been used.</p>
<div class="marks">[7]</div>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p>there is an Eulerian trail because \(G\) contains exactly two vertices of odd order <strong><em>A1</em></strong></p>
<p>there is no Eulerian circuit because \(G\) contains vertices of odd order <strong><em>A1</em></strong></p>
<p><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>the trail must start at B and end at E (or vice versa) <strong><em>(R1)</em></strong></p>
<p>BAFBCFECDE <strong><em>R1</em></strong></p>
<p><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p><img src="images/Schermafbeelding_2017-08-18_om_13.05.05.png" alt="M17/5/FURMA/HP2/ENG/TZ0/01.b/M"></p>
<p> </p>
<p><strong>Note:</strong> Award full marks if the correct path is given with correct total weight if an annotated graph is given that represents the Dijkstra algorithm.</p>
<p> </p>
<p><strong><em>[7 marks]</em></strong></p>
<div class="question_part_label">b.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.</div>
</div>
<br><hr><br><div class="specification">
<p class="p1">Consider the following weighted graph.</p>
<p class="p1" style="text-align: center;"><img src="images/Schermafbeelding_2017-02-08_om_16.38.29.png" alt="M16/5/FURMA/HP2/ENG/TZ0/01"></p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Determine whether or not the graph is Eulerian.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Determine whether or not the graph is Hamiltonian.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Use Kruskal’s algorithm to find a minimum weight spanning tree and state its weight.</p>
<div class="marks">[6]</div>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Deduce an upper bound for the total weight of a closed walk of minimum weight which <span class="s1">visits every vertex.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p class="p1">Explain how the result in part (b) can be used to find a different upper bound and state <span class="s1">its value.</span></p>
<div class="marks">[2]</div>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">the graph is not Eulerian <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">because the graph contains vertices of odd degree <span class="Apple-converted-space"> </span><strong><em>R1</em></strong></p>
<p class="p1"><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">the graph is Hamiltonian <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p2">because, for example, ABDFHGECA <span class="s1">is a Hamiltonian cycle <span class="Apple-converted-space"> </span><strong><em>R1</em></strong></span></p>
<p class="p1"><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">correctly start to use Kruskal’s algorithm DE(1) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>(M1)</em></strong></span></p>
<p class="p2"><span class="s2">BC(2), FG(2) </span>or vice-versa <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p2"><span class="s2">DC(3), AC(3) </span>or vice-versa <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1">GH(4) (rejecting AB<span class="s1">) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></span></p>
<p class="p1">DF(5) or EG(5) (rejecting BD<span class="s1">) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></span></p>
<p class="p2">total weight \( = 20\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p2"><strong><em>[6 marks]</em></strong></p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">the minimum weight spanning tree can be traversed twice <span class="Apple-converted-space"> </span><strong><em>(M1)</em></strong></p>
<p class="p2">so upper bound is \(2 \times 20 = 40\) <span class="Apple-converted-space"> </span><span class="s1"><strong><em>A1</em></strong></span></p>
<p class="p1"><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">the Hamiltonian cycle found in (b) is a closed walk visiting every vertex and hence can be applied here <span class="Apple-converted-space"> </span><strong><em>R1</em></strong></p>
<p class="p1">weight \( = 39\) <span class="Apple-converted-space"> </span><strong><em>A1</em></strong></p>
<p class="p1"><strong><em>[2 marks]</em></strong></p>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
<p class="p1">(a) and (b) were generally well done. A few candidates said that the graph was not Eulerian because it contained more than two odd vertices. A few candidates failed to back up their assertion that the graph was Hamiltonian by stating an example of a relevant cycle.</p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">(a) and (b) were generally well done. A few candidates said that the graph was not Eulerian because it contained more than two odd vertices. A few candidates failed to back up their assertion that the graph was Hamiltonian by stating an example of a relevant cycle.</p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p class="p1">In part (c) some candidates did not clearly indicate that they had used Kruskal's algorithm, but just drew a minimum spanning tree.</p>
<div class="question_part_label">c.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">e.</div>
</div>
<br><hr><br><div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">A connected planar graph has \(e\) edges, \(f\) faces and \(v\) vertices. Prove Euler’s </span><span style="font-family: times new roman,times; font-size: medium;">relation, that is \(v + f = e + 2\) .</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) A simple connected planar graph with \(v\) vertices, where \(v \ge 3\) , has no </span><span style="font-family: times new roman,times; font-size: medium;">circuit of length \(3\). Deduce that \(e \ge 2f\) and therefore that \(e \le 2v - 4\).</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Hence show that \({\kappa _{3,3}}\) is non-planar.</span></p>
<div class="marks">[9]</div>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p><span style="font-family: times new roman,times; font-size: medium;">The graph \(P\) has the following adjacency table, defined for vertices A to H, </span><span style="font-family: times new roman,times; font-size: medium;">where each element represents the number of edges between the respective </span><span style="font-family: times new roman,times; font-size: medium;">vertices.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><img src="images/prince.png" alt></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) Show that \(P\) is bipartite.</span></p>
<p><span style="font-family: times new roman,times; font-size: medium;">(ii) Show that the complement of \(P\) is connected but not planar.</span></p>
<div class="marks">[8]</div>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">consider the basic graph with just \(1\) vertex for which \(v = 1\) , \(f = 1\) and \(e = 0\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">for this case, \(v + f = e + 2 = 2\) so the result is true here <strong><em>M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Allow solutions which begin with a graph containing \(2\) vertices </span><span style="font-family: times new roman,times; font-size: medium;">and an edge joining them for which \(v = 2\) , \(f = 1\) and \(e = 1\) .</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">a graph can be extended as follows – there are three cases to consider</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">I – an extra edge is added joining two distinct existing vertices <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">II – an extra edge is added joining an existing vertex to itself, </span><span style="font-family: times new roman,times; font-size: medium;">forming a loop <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">in each case <strong><em>v</em></strong> remains the same and \(f\) and \(e\) each increase by \(1\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">both sides of the equation increase by \(1\) and the equation still holds <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">III – an extra vertex is added together with an edge joining this new vertex </span><span style="font-family: times new roman,times; font-size: medium;">to an existing vertex (which is necessary to keep the graph connected) <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">in this case, \(f\) remains the same and \(v\) and \(e\) each increase by \(1\)</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">both sides of the equation increase by \(1\) and the equation still holds <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">any graph can be constructed from the basic graph by combining these </span><span style="font-family: times new roman,times; font-size: medium;">operations, all of which result in Euler’s relation remaining valid <em><strong>R1</strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[8 marks]</span></strong></em></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) since the graph is simple there are no loops and no multiple edges </span><span style="font-family: times new roman,times; font-size: medium;">and thus no circuits of length \(1\) or \(2\) <em><strong>R1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">as we are told that there are no circuits of length 3, any face </span><span style="font-family: times new roman,times; font-size: medium;">must be surrounded by at least \(4\) edges <strong><em>R1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">since every edge is adjacent to \(2\) faces, <em><strong>R1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(2e = \sum {({\text{degrees of faces}}) \ge 4f} \) , <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">it follows that \(e \ge 2f\) <em><strong>AG</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">using Euler’s relation with \(f \le \frac{e}{2}\)</span><span style="font-family: times new roman,times; font-size: medium;"> , <em><strong>M1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(f = e - v + 2 \le \frac{e}{2}\) <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">giving \(e \le 2v - 4\) <em><strong>AG</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><em><strong> </strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) \({\kappa _{3,3}}\) </span><span style="font-family: times new roman,times; font-size: medium;">is simple and since it is bipartite it has no cycles of length \(3\) <em><strong>R1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">for \({\kappa _{3,3}}\) </span><span style="font-family: times new roman,times; font-size: medium;">, \(v = 6\) and \(e = 9\) <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">\(2v - 4 = 8\) so that the above inequality is not satisfied <em><strong>R1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">it follows that \({\kappa _{3,3}}\) </span><span style="font-family: times new roman,times; font-size: medium;">is not planar <strong><em>AG</em></strong></span></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;"> </span></em></strong></p>
<p><strong><em><span style="font-family: times new roman,times; font-size: medium;">[9 marks]</span></em></strong></p>
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(i) attempt to find disjoint sets of vertices <em><strong>(M1)</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">disjoint sets are {A, D, G, H} and {B, C, E, F} <strong><em>A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"><strong>Note</strong>: Accept graph with vertices coloured, or otherwise annotated.</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;"> </span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">(ii) let \(P'\) denote the complement of <em><strong>P</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">in \(P'\) , A is connected to D, E, F, G and H : B and C are connected to E</span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">therefore A is connected to all other vertices so \(P'\) is connected <strong><em> M1A1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">a complete graph with \(8\) vertices has \(28\) edges <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">since \(P\) has \(9\) edges, \(P'\) has \(19\) edges <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">consider \(e \le 3v - 6\) (the condition for a planar graph) <strong><em>M1</em></strong></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">for \({P'}\) , \(e = 19\) ; \(3v - 6 = 18\) so the condition is not satisfied <em><strong>A1</strong></em></span></p>
<p align="LEFT"><span style="font-family: times new roman,times; font-size: medium;">therefore \({P'}\) is not planar <em><strong>AG</strong></em></span></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;"> </span></strong></em></p>
<p><em><strong><span style="font-family: times new roman,times; font-size: medium;">[8 marks]</span></strong></em></p>
<div class="question_part_label">c.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">c.</div>
</div>
<br><hr><br><div class="specification">
<p>While on holiday Pauline visits the local museum. On the ground floor of the museum there are six rooms, A, B, C, D, E and F. The doorways between the rooms are indicated on the following floorplan.</p>
<p style="text-align: center;"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAU8AAADJCAYAAACjU7CDAAAXAElEQVR4Ae2dDXBVZXrH/zdYK4qoiFMTERmlCa67igZ0u+CCMEZju8JAhUqXjxLsohV3ZSTISqujBRH8mBVX3Uoi+MGIGCZxXSlUsqGGnVGS4uzSYjLYcYdsrq0SWERBp+R23gsnXk7uDecm59x7Pn7vTCb3nPOe9zzP73nv/7zn/Tg3lkgkEiJBAAIQgEBWBAqyyk1mCEAAAhBIEjgtlUMsFkvd5DMEIAABCJwgYH9Ip+VJ1YAABCDQCwIntTyt8+0Ka+3nv7sENm3apKlTpwre7nINcmnW0x91wj9RtGJit4iWp50I2xCAAAQcEEA8HUAiCwQgAAE7AcTTToRtCEAAAg4IIJ4OIJEFAhCAgJ0A4mknwjYEIAABBwQQTweQyAIBCEDATgDxtBNhGwIQgIADAoinA0hkgQAEIGAngHjaibANAQhAwAEBxNMBJLJAAAIQsBNAPO1E2IYABCDggADi6QASWSAAAQjYCSCediJsQwACEHBAAPF0AIksEIAABOwEEE87EbYhAAEIOCCAeDqARBYIQAACdgKIp50I2xCAAAQcEEA8HUAiCwQgAAE7AcTTToRtCEAAAg4IIJ4OIJEFAhCAgJ0A4mknwjYEIAABBwQQTweQyAIBCEDATgDxtBNhGwIQgIADAoinA0hkgQAEIGAngHjaibANAQhAwAEBxNMBJLJAAAK9JXBUrdXTFIvFevwrWlyvQ729RJ7OQzzzBN5ctry8XLt27cqjBVwaAl4TOEPFc19X4tgeVZUVqrBym/6YSCjR9XdMn+9Zq/J+XtvhfvnBFM/O32tTxSjdVP2hOt1nkrMS+/fvr5EjR+bselzI/wQsUfG/pW5ZWKABI/5SM0ed6VaBOSsnkOLZuXebflHdrK0bfqO9QVbPnIWZC0HApwQ6W1VX16HvT/muBvrUxExmBVA8D2rXm/+pG1b9gwq3/qsa9x7N5Bv7IQABnxPojO9R88FgtoCCJ56H/kOvN1yhKfOmaGbhRi2t+k3gOpp9Xp89Mu8z1S8e1eOgQSw2TdWt3Aw9CoAvio2vnKhzUgaP+g25U+8d84VpWRsRMPE8qtY3XpcW3qric6/UTTNLFX/5HTUdCuadK+toBfqEwZrwWJMSf9ymykJ1Hzg41qZtS/5ELW2HA+0lxvdM4OQBIzNY9JhKAzhYZLwMlnh2fqzGHd/StGsHSRqs8RV3qSy+VVuaOnqOGEf9T6DgIo2fc6su9L+lWOgagQINKL5O150bLBmy3A+Q1Z061LBem8aU6eoBx80uGP49TS9r18uv/rv+QOPTimkA/x/VR83/pcPF03XvhMEBtB+Te02goFiTJhUHrBV33NsAiWeHmra8rV9VXK5+Vp9Jv8tVsTWuePVr2sLAUa/rb95PPPxbvfnr/827GRiQRwKHd6u+OVhPkIERz87WN/WkVtom2CZ0rK1GcwsbtaHx40DP+cxjtc3LpU8aODj7Oq36lEeHvATCBxftjO/QUz+uk/78XB9Y49yEgIinmZ7UoikV3+s2F6zgou/rb2cWMefTecx9kfOkgYPPf6dHS/7UF3ZhhNsETizPtJ4SbaPtZtlmv6KxWjX4LzRqYEDk6ASiAFj7teL1P9N9T/bTsAtPTxPZARpScqm0dal+tPTfFKcBk4aRz3cNGK6xV53ncyMxr3cETizP7FqOmbo085vP7Y9N6NYw6t31cneWz8XT3LV+qKKJD6kh/qgmnvM3tnmA5vgslVRslBRXw6NlKhryU9UzdSl3NciVK52hy0q/FbgvjyuuU0hgCZzmb8tP3LXmZrLyVMczncd+CEAAAn0j4POWZ9+c42wIQAACXhFAPL0iS7k2AieWZ54zUSvj0vHR9lFaXP+ZLR+bEAgGgVjCvAPrRDIjXyal7LIO8R8CEIBAJAlk0kVanpGsDjgNAQj0lQDi2VeCnA8BCESSAOIZybDjNAQg0FcCiGdfCXI+BCAQSQKIZyTDjtMQgEBfCSCefSXI+RCAQCQJIJ55DHtHR4fa2tryaAGX9huBjz76SLt37/abWdiThgDimQaK17uMaD7zzDM6//zzdfHFF3t9OcoPAAEjmtOmTdPw4cN14403BsBiTEQ8c1gHjhw5ok2bNunmm2/WggULNHr06BxenUv5kUCqaG7cuFFXXnmlPvnkEz+aik02AoinDYgXm5Zojhs3TlOnTtX48ePV0tKi+++/34vLUWYACJinj8rKSl111VUyomlam3v37tWDDz4YAOsx0RBAPD2sB5lEc+XKlSouLvbwyhTtVwKWaA4dOlSrVq3SFVdcoS1btmjr1q267LLL/Go2dqUhgHimgeLGLvNlsLc0EU03yAazjEyi+d5776msrCyYTkXcap+/zzN40dmxY0eyRVFXV6dJkyZp165dGjlyZPAcwWLXCJhH8SeeeEJffPGFrr32Wj3yyCMIpmt081cQLU+X2BvRnDx5ssaOHZsssbGxUbW1tQinS3yDWMzzzz+voqIiPfzwwxo4cKBee+010dIMYiTT24x4pufieG8m0RwzZozjMsgYLgKWaN55551Jx5577jm1t7dr+vTp4XI04t4gnr2sAK2trcnRUtPSNF8Mq6WJaPYSaAhOyySa8+fPD4F3uGAngHjaiZxi2xLNkpISNTQ0qKamRtu3bxeieQpwIT5sBgdHjBghe0sT0Qxx0CUxYOQwvmbaken4N9NLzOR2I5rl5eXq37+/wxLIFjYCZoL7jBkz9P777+uss87SokWLknN3Bw0aFDZX8ScNAcQzDZR0u/bv368DBw4gmungRHRfU1OT9u3bh2hGNP6Ip8PADxkyRC+88ILD3GSLAgEzAMQgUBQind5H+jzTc2EvBCAAgR4JIJ494uEgBCAAgfQEEM/0XNgLAQhAoEcCiGePeDgIAQhAID0BxDM9F/ZCAAIQ6JGAb8TTLHM0fyTnBMyLlc2kfdLJBMyk9bBxMfOMX3rpJZn/YUomTqYeBzH5RjzN24fMUkfz6i6SMwKbN29OLhF1ljs6uZ599tkklzAJjZlnPHv27OSLk8MUSfN7TeYF4UH83vtGPM1KDZPWr18fprrhqS9z5syRefVdUO/cXsF56KGHklzMzSUsycwzNiuYjIAGUWgyxcH8qoJJb731VqYsvt3vG/E0S9pWr16d/G2fMFUOLyNv1tObd4auWLEidI9zfeFm3p9qhCaoLZpMvls/2xKmBob53ptYmR9EDFryjXgacLQ+s68+5u30O3fuVJhaWdlT6H7GPffck9xp3nQUlpTawAhTn65pAJg6/MEHHwQqVL4Sz9TKQevTWT0yv4Vk7ty0Pk/mZR5z161bpwceeCBUg0cVFRXJF9OsWbPmZIcDvGWeoMzLdt5+++1AeeEr8TTkaH1mX3/mzZtH6zMNtttuuy35pTS/UhmWZN7iZR7fzdu9wtT6nDVrVvJGF6RGk+/Ek9Zn9l/z1NZnkCpf9p5md4YRmqeeeio5eGSmL4UlmVchmpZamG4K5idsTDLvyA1K8p14GnC0PrOvPlbrM0yDCdlT6H6GeSQ0bJYuXRqaQbXUm0JY5kabbhYTJzOXNTApkZIkJcyfH9Lq1auTtuzfv98P5nhiQ01Njau8ly1bFnpmvQlES0tLkoupU35P2dSJSZMmJUaPHp348ssv/e6WI/saGxuTcdq1a5ej/LnKlEkXfdnyNHceWp/Z33+tn32g9XkyO9OtYU2DC1M/oZnPGqaZFtdcc00ycOb3wIKQfCue9H1mX31glpmZuRmbfsIwjVJb81nDMtPCdEdYN7kgrA7zrXiarwGtz8xikOmIxSxM8xsz+ZrNfnNjsUapw9JPaPy3+rqrqqqyweHbvGVlZUnb3n33Xd/a2GVYar9Bpmf71Dy5/hzmvs9s+rey4W4xM319pJMJ+L2fsDd1wop3WMYHTIzMn19SJl30dcvTKLzVkqIfr+t+d8oPYZxIfUqnHWYIWz+hcdv6jpjH9zCku+66Kzm9rK2tzdfu+F486cfLvv6EdSJ19iS6n2H1E4Zp3bv5jpjVVGGZOH/99dcnA1dbW9s9gD7a43vxNKysOyutT+c1x5pIHaYBEufe95zTesFGWFpqxltrNVUY4m1u/suWLfP/+0tT+xUyPdun5snX57D16xiOvenfyoa/VT59n92p+ZWNZVd3i0+9xzrXzJcMejJzPY0e+cGXTLoYiJanubPS+uy5NZXuqNX6DNMyvnR+9mZfGNkYn8wbiszje9CT6V4xvqxdu9a/rqTeoTIpbGqefH4OW+vTail4yXTLli2+uYN76WdvyrZWtJg4+CX1tU5YPpm4Bz1ZLPbt25dXVzLpYmBanub2Q+sz+5uwmTcXltZI9t73fIZZ9269zi8sL1QJ01p+6y3z9fX1PQcyT0dPS3ddPz/mmVUiCxYsSAqpGWX0IpmXE5jfVvE6WUsFc8Hb/FyHmRxuvlxepFgs5kWxXWUakfMimRiYJY5mMPLuu+/24hJavny5Dh486KhsN+rEp59+mvTJTDS3Jp07ungWmcxbqt55550szuh9VvOWefPKOreSW3U1rXi6ZaQX5Zi7kXl9lVfC6YXNmcosLCzULbfckumwa/utV9ZdcsklrpUZloIsNldffbVnLpk3BjkVT1MnrCes3hpk+TRs2LDeFnHK8/pa9oEDB5JLZc0KqfPOOy/j9cxNc+jQoRmP9+ZAIpGQGwIaM50JlgFWgSm7rEP8h0BeCFAn84Ld84uaFnZJSYlaWlpkxN7PKVMdDFSfp58BYxsEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EICASwQQT5dAUgwEIBAtAohntOKNtxCAgEsEEE+XQFIMBCAQLQKIZ7TijbcQgIBLBBBPl0BSDAQgEC0CiGe04o23EPAFgTPPPDNph/XfF0ZlaUQskUgkrHNisVjyY8ou6xD/IQABCLhKoKOjQ4MGDXK1TC8Ky6SLiKcXtCkTAhAIDYFM4slje2hCjCMQgEAuCSCeuaTNtSAAgdAQQDxDE0ocgQAEckkA8cwlba4FAQiEhgDiGZpQ4ggEIJBLAohnLmlzLQhAIDQEEM/QhBJHIACBXBJAPHNJm2tBAAKhIYB4hiaUOOIvAl8r3vy23nh8topiMZmJ1rEbFqu6rlnx/2tVXV2rOv1lcACt6dSh+p9+w9fi3PW/SDcsfkGb6lt12APvEE8PoFJkxAl0xvX+U3eo9Acb9PGl96j5WEJmyXNi20901bFf6/6h4/XsfqSz77WkQAMnLFd74lNtqyyVyqrUYrFOHNPnLa9opt7Q1IklKp69Th8edpc54tkVwVPdxb6j2Y9vUH3roa4z+ACB7gS+1h9ql2nywv1a+Muf6b4ppSq0vmUFhSqdslA//+UiqaXdk9ZQd3uiuqdAA4onaO5jG7Wnaq700hLd+XyTq8ytsEaVcIrfPd3FvlJ7U6Uu/NW9mjj+XlV/iICmgONjKoFDjXr67p9LlQv196Xnph458blAA0pnasl1x98qlCYDu1wlMFAj5vyTnpl7vhoWPa7XW4+6Vjri6Qjl6SosnalHf/HPKotXa+mLTUI+HYGLWKajan3jea2MF+o7JUUakNH7wRo/5bsamPE4B1wlUPBn+vaYyyU1akPjx671NSOerkaJwqJN4LDaWv5bUpFGDhssvlx+qQ2n68Jhw1WouH7nYnfJaX5xz+92dMbf18tVG7S1cK6q/m4UrQa/Bwz7IOAxAcQzE+CtFSrpV2E7WqrKba9q7ggeuGxg2EwSGKAhJZdKMq1Pkn8IfK1PPt6ruApV1mN3SnYW82SRiddJ0x7MgFGNVs36Sisn3qDZ1btdHbXLZAL7g0bgDA0fe7PK1KyXt/yWfnG/hK/zf7R7xx6pcIp+dNOlrnWnIJ6OAmwGjKbovhc3qqpsv16qeNjVUTtHJpApEAQKim/V4spSxVc+qX9pPpje5s64mhu8mbid/oJR3ntIH659WHdX79f4hbNUdtHprsFAPLNBWTBYw0YWJR/LWtq8WLOQjTHk9SeBwZrwj2tVNev3WjRquhZX16u1a3J2pw631mvd2madNWp4D6Px/vQsWFYdZ129+DZdXrFZJUvWaf3Ca11ljnhmUyM6v9DBz76SdKlKhmSeiJJNkeQNIYEB39bcF7eqqfavpZd/qJKz+51YnrlEr+85R2Vz/kojBvDV63vkrYUtF2jiymYpOU5xYilsrJ/OLvmxtl8wW7VNzdq2/MZvFiv0/cLJEhgwcgiyM96s2lefPt78X3KHyoef4fBMskWSgFlNNOmO5N9jkQSQC6ethS3Lc3Gxbtfg1zO7kJi72FKNmPio4l37bB/GV6rqJ9NU/oOUJXe2LGxCAALhIpDp1zMRz3DFGW8gAAGXCWQSTzpeXAZNcRCAQDQIIJ7RiHMgvdyxY8fxgZZYLJD2Y3RmAsn3m8Zi6ujoyJzJ50cQT58HKIrmGdGcPHmyxo4dG0X3Q+2zFVvLyUGDBlkfA/cf8QxcyMJrcGtrqyorK5Oi2d7ersbGxvA6GzHPLNEM0w0R8YxYJfaju5ZolpSUqKGhQTU1Ndq+fbvGjBnjR3OxKQsCVmyNaFo3xNra2ixK8G9W5nn6Nzaht8x8sdasWaNVq1Zp9OjRSdEsLy9X//79Q+972B2MQmwRz7DXYh/619bWpqeffhrR9GFs+mpSFETTYoR4WiT47zkBM7K6fv16LViwIHmt1atXq6Kigpam5+S9v4CJ7YoVKyJ1Q0Q8va9Xkb9COtGcMWOGgjzSGvmgngCQLrZRuSEinnwLPCOQ7ouFaHqGO6cFE1sJ8cxplYvGxY4cOaLNmzdr6tSpSYfN4zmiGY7YI5rfxBHx/IYFn/pIwBJN0/e1c+dOLVq0SPPmzVNxcXEfS+b0fBOwx3bZsmWaP39+pLteEM9818oQXf/2229XXV1dUjRfeeUVRDNEsR03blzXDZHYHg8sb1UKUQXPtytmFckFF1zgqmhmeqNNvn2N2vXdjm2Q4prJVsQzat+CgPmbqeIGzA3MtREIUlwz2cryTFtQ2YQABCDghADi6YQSeSAAAQjYCCCeNiBsQgACEHBCAPF0Qok8EIAABGwEEE8bEDYhAAEIOCGAeDqhRB4IQAACNgKIpw0ImxCAAAScEEA8nVAiDwQgAAEbAcTTBoRNCEAAAk4IIJ5OKJEHAhCAgI0A4mkDwiYEIAABJwQQTyeUyAMBCEDARgDxtAFhEwIQgIATAoinE0rkgQAEIGAjgHjagLAJAQhAwAkBxNMJJfJAAAIQsBFAPG1A2IQABCDghADi6YQSeSAAAQjYCCCeNiBsQgACEHBCAPF0Qok8EIAABGwEEE8bEDYhAAEIOCGAeDqhRB4IQAACNgKIpw0ImxCAAAScEEA8nVAiDwQgAAEbAcTTBoRNCEAAAk4IIJ5OKJEHAhCAgI0A4mkDwiYEIAABJwQQTyeUyAMBCEDARuA023ZyMxaLpdvNPgjkjQB1Mm/oPb1wkONKy9PTqkHhEIBAWAmc1PJMJBJh9RO/IAABCLhKgJanqzgpDAIQiAoBxDMqkcZPCEDAVQKIp6s4KQwCEIgKgf8HvIisxMfyM/0AAAAASUVORK5CYII="></p>
</div>
<div class="specification">
<p>There are 6 museum s in 6 towns in the area where Pauline is on holiday. The 6 towns and the roads connecting them can be represented by a graph. Each vertex represents a town, each edge represents a road and the weight of each edge is the distance between the towns using that road. The information is shown in the adjacency table.</p>
<p style="text-align: center;"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAr0AAAC1CAYAAABS6EecAAAgAElEQVR4Ae2dDXRU1b32nxl8kbc3Ri8XLWeCryyZlWAl3C6SxlvM244JTvRaLeXTaiGQLAsVpEsWmZhUVMQS87HC1QUtaickoFxJIYWqVzMyY+wF+5I7QSoqZG608TaZcRVKSZgqsDrnvOtMvs5MJkMMM2fmnDyzVlb27H1mf/yes/f+n3P+ex+DJEkS+CEBEiABEiABEiABEiABHRMw6rhtbBoJkAAJkAAJkAAJkAAJBAlcpeRgMBiUXxkmARIgARIgARIgARIgAc0SUDo0hBi9coJs+CoP0GwrdVBxapE8IlILapE8BJKnJuwX1CJ5CCRPTdgvkksLZW3o3qCkwTAJkAAJkAAJkAAJkIAuCdDo1aWsbBQJkAAJkAAJkAAJkICSAI1eJQ2GSYAESIAESIAESIAEdEmARq8uZWWjSIAESIAESIAESIAElARo9CppMEwCJEACJEACJEACJKBLAjo3ei+hu2ktTHdsRZtf1KWAbBQJkAAJkAAJkAAJkMDlCcTZ6L0AT92S4DZo8hYefX/ZKHWdUdTsDFyl2YpjlqDOc0GRzmDSExBPoa7ApNDQAIOpHK7egQsNEb2ucpgGzwEDDAV18AwkJ30DtVRB9rnEqxVBA7k/nPt4eD8Z7AfhfYTjYGx1DJ9n+uejQf7h6SYU1J0Ch6jYqtCXW4T+YTDAVOpCb39xoqcOBcr5wsD+EA8lhvIMH38G7DXFf1Mx6k4NKDT0S82F5NcQKz+AvE1vbD8Br0MqswgShDXS/q6LETLvkU7ai6QZy7dJR72R0iP8JFJU4H+kd975VApEStNgXDy0iCeGQLtdsmKWVLS/cwQNTktO2yrJ3v5lPKsRl7w1p4VafS4utKNnqhUtAl37pSIBEqx2qX1wUOob6wQIktV+clg/CfYhy1OS80rGwej4YpqqFS36Gh2Qzrfvl2zyXARIgs0p9YTQ+FJqty+WYCmT9reHpoQclqRftKWFJAW8h6Xa5bMkIEuyOU8Pp9rjlGyCVbLVH5W8g/1n+GHJGKM1LSTpS6m9/hmp9qg3bEy6KHXtXyMJUef1ZFRgqE7hWsT5Tm/fNYBRyMdjG1dA8P0Z5/4W6dp5IoxIQ/nPipEjTBzjhYMI//u/we5PL47x9/xZbAhcjSnX/QNUObFiU2Fd5qJOn9Mlupg1ypj2ryh9ZjFwogNdg+5VqZi5ogTPWIETRz6GL2Q4FOHv6sT/WrYUljGPgzGrvg4zMiIlfQEq9jSgzCLAV1WLF9vO9bdThL/tl1i1+1Y49zyFBempOmx/cjXJKNyOR7fbUW3xoqryt2FP/i6h+1Azera9iIrCHAicUOIsnh/ea/JRnCMo5m4R/lP/jvK124GiTXh6/k2KtDhXJ47Zq3QqGZGaMx/rLcew+7cfwB/eILETh1tnINc8KTxl9N/9buzY8Dy6Rv8LHkkCOiagQp/TMb3YNG0SzLl3wepzoNl9dihL43TkLs2Fr+5VNHcoXbnOwt38ZyzIna6LyWWowckVki8Iy39ZgeXCGyjZsDO43kP0ObGl/DM88nIZ8njBoZ5gKdn4sXxDzLEVlQc+G3QnEbtfx2bHbdioE0NLPaBjLSkV3/h2OlKUP5dtqp+UYVdGLV57bj7SVLIWlVWIR1i9ZqTMxn3L5qCl9gBaB3095SaJ6G3Zj1arBeZgbUT4Pc2oKczs8xE1FaLmbU+/oSyntWBfTSHMpf+BU63bUWjKRGHN8yi9dz5KWj6Bo/gWTDD0+w37PXDtq0GhWelfKpfZC8/bW1Fo6vNXMRVuR6vvkoJvePpWvO0Z8GWR69CE0jtMMMh1a/pPtLR+POiLpMiEQRJILIFR97nEVlPPpRvNc7HU6sXu5g8UY4QfXe2fAjiMvYc7Byd69H6A5o9yruziX88wY9Y2I1Jm/hBbtq2B0FKNDdteQf2mN2B+7mksSBvrk8aYVW6cZWREqmUVthUBdWurcaD7EiB+hgObj8K68Xu6MbSSX9SJuEGYrLjYPoe2HU+jpGUOqmtWIitFPVMx3qxUbMkkpC9aDRvqUbnPMzTQ4yzchyZgybwbYYT8iOlFbH4jBQ/uPAFJCuC8Kw8nCh/AZnnxW28LNlvuwOKSXfji8z+i98bFWLfejP/Bv2Cj0wW7dQas9pMISG5U5gGuzQ8gf3EJdn2hxHgObTWFWPXOLDzbJUEKdGLbVTtw24qX+x+vnEPb1hq8ce392OmVIEk9cH33QxRanu1bmCV60Lj+d7jt5U5I3gZsmP9/0HPyr8oCGCaBJCEwmj6XJFXVazUG7uruPgT3wMV+7wc4hEWosAKOve+hI+jiIKLX3YKPFsztv/jXK5BkaddEpC14Bq9Vz0FLWSn25qzGipl0aUiIOsabMP/pTSjCdqx9/hA+PvALOKwPYz4vQBIiB3AJPtdz2FDyGZbbn8XqrOsSVI/4FKui0QsgdTYKlpng2P0m3u/3cRO7f4dG5CA7Va7KWbQ2/gpV63NhmiDfhZ2Aa25ZgV2+tr47Jal5qDzlhE0AMPUWzBRuQNaG3+CdDTmht+WDrKYgr/Iw2u2LQ8n1HkPjjluw8bH8Pj8ho4Bvr1qN5ejB+S9EQE6v3oz1t5kwIbh69FrcUlwHX/8jSrHjPew99ld8evREnz+e8SZ8v/B2cLgMxcxvSULgsn0uSeqp22qEuzjIxm0rUPAgFizNBRxv4XDQxYGuDeqfAl+Dac63YIEvZE5Svx4sccD/3Vd1D259IQPr6daQsJNCdi15/EdPob1oE7asmBXBtkpY1WJSsLpGL6bAUvwwrC11+IXjTxBxAR3NDlw7b3af0Sg/3tt9M+ztX8pbSIT8eSvzYmBYyhPOIewOufM7EULOGjQ0P4qsFPSlZ9rRHggtXwrePZ4Cozkfq+4+hpKF2chaWYN9rgHXi5jowUxIIMYELtPnYlwasxtOINTFQX6yBczLTuvz9x1wcaBrw3BwcY6RJ/dNjbfil0drYZHdHHa4h683iXMdmP0Agf6nUoIA61I+7Rigovp/2bXkiSdRhzXY9rQ+3UtUNnrRZzTK/jsvONHxd3kB27dRbJmi0DbMz02RErOg7wMc++8BH90IuQ7efYmQZrwJC15ywH3gRSz7n1oszs9AenETukNWYUf43TiIMk6djm8KXhzvPKNwX1E0XDyDzo9uwPSp9JtTUIl7MHihFrXPxb0K47sApYvDn97Hof4nW33GsOzi8J9wH6Vrg6onib8VteVdeKhmAWbmrESN7OZQshFbXN2Rxy5VK8fCSCARBM6hrXYNFtaZUPZyWQT3kgvw+/+eiIrFtEzVjV4Yb8S8B+8NrtbcVPwEmnJuG/JhG3gUW/xTlDW0KrbzOYf3XX9QLAQZKwMjUqaZkQl51W4VmgYXpwHwfwhX2zmkZs/DMuHXKF71JBrafEMDYDC9fwW2UUDW9x9C5Tud8B7dhjvf3ILnW5Qv3Bhr/TT+u379TrR7I94xEX0fo3W2pd+VReNt1VL1o/U5LbVDs3UdcHF4DfbHXwUGnmz1G8NwvIDSLZ9x1wa19BW74ap6HZPLVvQv0LkOWaufhX25FxU/quhbTKVWXVgOCSQFAXk91U5sKDkGS/VmlOelKRa19VVQ9LwLp5dG7xjkGthK6S/YswthA/1k5Cx5EBY4ULXitn6/Xtm390dwXnvTKNwbvkDQ4PL/AQddsvvE8I8xfQG2VN8DtFRgYca1Q28Ru/dtXJtxHZA6B0vWy+lVWJE94NdrgGEgvff/oWnQwJ2Ir6cJuAo3I2NayGYfwwseFzGTkbPyEdy5+6d4pKYZnsG9SXvhcdWhrMiBnOXZo9BxXMBSsZHR+pyK1RjHRfXd1f0L9rz9dczLntxPYhLMBfejSGhDy8TvcteGuJ8fl+Bra0LNyiI0W9ahSLlwLeUbWFR4LwTfdiz81kPY2qq44RH3erEAJYFLZ3sR4oGoTGQ4PgSCW75Wo8VSgprV2cP8eEXfETxX6cY1enhKO/Teir5Q+NsrwtNj873/zTchbyoayPmi5HXvGnxrDoTlUrWjXTovSVLfG78QfJsO5lokyz3KNx1dlLzOpyQLBMlS5pC8AfntX1l9x0L+zeKhN4EFvJK73iZZgvGCZLHZJafyDTwh6ZCE5bWSYyC954TkPPCGtN/e/3uLTap3h7/FZKAtV/ZfHS2urI7Dfy2/9cgp2W1WBftZ0vLqV0MZD/9hUsdoUwsl0mh9Tnlc8oe1qUUf/+FvAZPHqbkR386W/EpIwT6uhXpKgZOS3dr3Jjb5/Al9C1hA6nGWSUIwvn9+kcMR56fkba02+4XMM3yuDtcneZmPVDNtaRGJv6IfDPQLjfWHAW3CtTDICcpLB4PBEFxApoxjODEEqEViuEcqlVpEopKYOGqRGO6RSqUWkagkJo5aJIZ7pFKpRSQqiYkL10J9n97EtJulkgAJkAAJkAAJkAAJjGMCNHrHsfhsOgmQAAmQAAmQAAmMFwI0eseL0mwnCZAACZAACZAACYxjAjR6x7H4bDoJkAAJkAAJkAAJjBcCIQvZZIdffkiABEiABEiABEiABEhADwSU+zVcpWyQnBC+0k2ZzrC6BKiFuryjlUYtotFRN41aqMs7WmnUIhodddOohbq8o5VGLaLRUTdN1kL5oXuDkgbDJEACJEACJEACJEACuiRAo1eXsrJRJEACJEACJEACJEACSgI0epU0GCYBEiABEiABEiABEtAlARq9upSVjSIBEiABEiABEiABElASoNGrpMEwCZAACZAACZAACZCALglo1+gVT6GuwBTcbUJenRf8M5XD1Sv2CyWi11UO00Ca/L+gDp6BZF3KyUaRAAC/B66mPagpLECp60wEJL3wuA5iX00hzKUu9EY4glGxICDC72lB074aFJqVY5My70vwte1G6R3yWJaJwq1H4OMYpQQUh3CEuWFwnliCOs+FOJTJLEMIcIwKwZG4L5ebC+QxrBk1hZn9tlYBShtaNT1GadfoNc5EUbMXgXY7rJiFov2dCHi3IC91oElGpOZtgVc6DadtFeztX0JqLkL6QHLizjKWTALxIyBfDN7/OBr2V6Bk118ilHMBnrpHsamhHutKduGLCEcwKjYERE897t+0E/vXlWBXRNAi/G3b8cCGT1GwpxNS4C0Unq7AA7Wt8MemCswlIoGzcDc74IuUZr0LueZJkVIYFysCHKNiRfIK87n8XCB2v4WX3gDu2/4HSNJFeI/eh8/L5mt6jNKJCXg1plz3D9BJY67wRObPxzUB+WLw9UbsfPJRWCOCmIT0Ijte2VmBZ6xCxCMYGRsCxvQivP7KC3jymcWRMxQ9aCzfh5yNa5AnTASMach7bD1yamvQyLuNkZnFIrb3Qxy7ugLegAR5b/q+vwB6nBtxz9K5MHMiiQXlkfPgGDUyG1VTLjcXXMAf/3sylvy0AOkpcqeYCCGnGD97JhcttQfQOvhUXdVKX3Fh7N5XjJAZkAAJkMBXJyB2vIe9jjRkTEsZ+nHqbBQs68bew52gl8MQlliGxL/diB/Y8iEoZz/Rg32Vn2BB7nTePIklbOalYQKTMMPyL0hT9hNMxNTpZmj5dklIczSsDqtOAiRAAhoicAEdh9+CQzBj+tSJYfW+CMfe99BBqzeMS2y+GoUZmBG8czWUn3wB0jRtIQro2jAEhSESGIHA1+7ORkZYHxrh0KSLptGbdJKwQiRAAvon4EdX+6dAphnTNDp56Ecj+QKkFbc++J2wu1r6aSFbQgKxISD7w3dj9cN5mu0rNHpjcyYwFxIgARIgAS0SEDtxuOkGFGRP1mLtWWcSUImAvPB2DxquX4PVWdepVGbsi6HRG3umzBFn4CrNjrKdHBGRwHgnkIJpGTcDJzrQ5acfQyLPhqBrw60WZA/u/JPI2rBsEkhSAn43Xmr8R5StzoZiFUKSVnbkamne6DVOnY5vCl4c7zwTeeGHeAadH90QwW9uZChMIQESIIH4EpgEc+5dw3fYkMer4+dg5S4C8cU/mHu/a0PBbKQOxjFAAiQQQkD8DAdf+iPu3vggZmrcHUvzRi+Cq51NONHujbi3pej7GK2zeRUfcgLH/csU5FW6FdsBSZBC9lCOewVYAAkkPQGjeS6WZr6LZvfZobr6vWg/MQdLuYvAEJN4hujaEE+6zFsPBMRuuJ57E9fc/4Mhg9f/IRrqjmjyxUbaN3oxGTkrH8Gdu3+KR2qa4Rl8VCi/aaQOZUUO5CzP5lW8Hjof20ACeiJgTMeSLYvQunk7XL5LgDy5PFuL1vUbsCSdL0hQQ2q6NqhBmWVoloD/FJrKipC//ifIN1095LJ4jRV78E/adHOQwj6AfINOa5+AdL7dKdltVkmuf9/fLGl59auSs71Ha40ZrK82tRisvq4C2tHitOS0ZSn6ASRY7VJ7YECOgNTjLJOEwX4i95fFkr39y4EDkv6/ZrTocUo2YWA8kv8LktV+UhqUIkj6ouQ9uk1aHjzOKtnqj0re0AOSWg/NaBGR4pdSu90mVbv/GjFVa5Ha0YJjVHKcW5eZCwKd0v6iWaFzyeC8oZ05I7xfGGT4yqsQg8EQfCytjGM4MQSoRWK4RyqVWkSikpg4apEY7pFKpRaRqCQmjlokhnukUqlFJCqJiQvXQgfuDYkByVJJgARIgARIgARIgAS0Q4BGr3a0Yk1JgARIgARIgARIgATGSIBG7xjB8WckQAIkQAIkQAIkQALaIUCjVztasaYkQAIkQAIkQAIkQAJjJECjd4zg+DMSIAESIAESIAESIAHtEAjZvUFe5cYPCZAACZAACZAACZAACeiBgHKTsquUDZITwrd3UKYzrC4BaqEu72ilUYtodNRNoxbq8o5WGrWIRkfdNGqhLu9opVGLaHTUTZO1UH7o3qCkwTAJkAAJkAAJkAAJkIAuCdDo1aWsbBQJkAAJkAAJkAAJkICSAI1eJQ2GSYAESIAESIAESIAEdEmARq8uZWWjSIAESIAESIAESIAElARo9CppMEwCJEACJEACJEACJKBLAho2ei/AU7ckuNuEvDqv7y8bpa4zCqHOwFWarThmCeo8FxTpDMaMgN8DV9Me1BQWhGkwUEIvPK6D2FdTCHOpC70D0fxPAuOKQPiYZEJB3SmI44pBIhorwu9pQdO+GhSay+HqjUBc9KF1ayFMwfmkAKVNp+BPRFXHdZmX0N20FqaCOngiSDSu0ajceNHXhoNyfzEZYDCN0GdUrlMsitOw0TsJ6UWNCHgdKLMIgLAG+7veQ2XeFAWXKcirdOGkvQgzlm/DUe/LKEqfpEhnMCYExFOou/9xNOyvQMmuv0TIUr5AeRSbGuqxrmQXvohwBKNIYDwQELt/h1d2tymamouludOh4YFY0ZbkDYqeety/aSf2ryvBrogD0Dm8f+AIcP9L8EoX4T16Hz5f+yNsDrmJkrzt00vNxO7X8cTa7fDppUGabMcl+Fq3Y2XWCjR13ojClh5I3i3IS9XHKKX5VhiFfDy2cQUE359x7m+RLg0nwog0lP+sGDnCRE2egklfaeNMFL3eiJ1PPgprxMrKFyh2vLKzAs9YhYhHMJIE9E/gHN7/94OY8vJpyHui9/018kJcBeGN6UV4/ZUX8OQziyOWJn7yEXpuu69/jpgIIWcpCpcBu5s/4FOpiMTiEOlvRW357zDlzllxyJxZjo6ACH/bdjwwvxXfPODAzg1LkZeeOrqfauQozRu9gBGpOfOx3nIMu3/7wfDHUWInDrfOQK6Zd3g1ck6ymiSgTwK9x9BYuwtVm6tR19QCjz/SRbo+m57srTLOuB2WNMVNEfEMOo/fiPVL5kBfU36yKnEObTv2AOseRsHUq5O1kvqvl9+NHRtewc3bnsZPcwRdPoHSgdELIGU27ls2By21B9Aa4qslordlP1qtFpj10VL9dzq2kAR0SeACPPt2oEp+bttSheKFdyDj3sfR5KF3e3LJLfv+ulBX9m/oKN2G9VnXJVf1dFkb+e7iLjyPB7A6a7IuW6iNRl2Ap7EGJcjH7eKvsVL25TVkorCmWVcX6DoxBSchfdFq2FCPyn0exaKQs3AfmoAl827U5RWLNjoSa0kCJAD0rUGQZH9R92uw26xASwUWrrKjjXd8k+QEkRcZ5uCajHwUV/0Wv28+ig5qE39t5LuLzwPrVmcjJf6lsYSRCMhPxfcegyVnFv759nVo8AZw/uQGoHYlVu1wD3+KPlI+SR6vE6MXQOpsFCwzwbH7TbzfP1DJi0YakYNsnThgJ/m5xOqRAAlclsBECFnfQ1Hla/A6n4Kl5RU0tp697K94gBoE5IXPbkgBL9z1y4CqhbD89AC66YUSR/jn0PaSCzdvWY2sFP2YI3EEFr+s/V60n7gOOQV3Iyu4/smIlJlL8bNnctFSUoNGnex8paOzbAosxQ/D2lKHXzj+BBEX0NHswLXzZtMnK37dhDknPYHwLbL0tf1M0uMfsYITIeStwUYbF0uNiChRCUYBWYWb8IJ9MXxvutHOu71xUkJ2a3gV+2/6IeYr/anjVBqzjU5A/LwTx4dtmzEJ5ty7YMWnaO/SxwZ+OjJ6AaM5H6uKgLoXnOj4u7yA7dsotii3MIsuOlNJgARIQD0CKZiWkYHMDBMf66oHfZQlDUz2ozych42BwFm0Nv4KFQunY8LgXvvXI7+qDXAUI2MC97AeA9Qx/8Q4dTq+KXhxvPOMwkV0ILubkTFNH84nujJ6YbwR8x68F4JjKzYVP4GmnNu4gG3gnOX/cUqg/5Ht4BZZkq72XNS2qH50dWSidFE61xwknZAi/F0d+OTubGTwsXuc1IkwNkmn4bRlAVY72gNeNBfNZN+IE/1h2fa7iJ448jF8gy49ff3ghPUu3eyApS+jd3D7sr9gzy5gATd9H3ZeM4IESCABBEQf2g7+B9p8l/oKD779qxYt85bBwjUHCRBEWWT/W8DuKEVDmy94l0v0OfFs5VmUl8xDms5mSWXLGSaBIQJTYFlXjrvffBLl9R8GF66Jvt/D3vAZ1m9ZgHSd9AOdNGNItr7ty3IBHV2ZKFqXpME+v9EJGcVwoA1V+dfDEPIaSRG9rnKYJtyCYocPvqp8XGvgK6GTVExWKy4ERPQcfQ7Zpqv7tgGq/R389zyGp/PSeCcrLrzDMu11odT0v5FR/GvAV4H8a6cpXv98Fa79xrdwZ3sVVmSbMMGQiZWvnMfC+udRNJO79IaR5FcdEzCmzcdzLTXIfPeHuMZgwIQHfovJ62p0tXWfQZJfC6T4GAyG4JuCFFEMJogAtUgQ+AjFUosIUBIURS0SBD5CsdQiApQERVGLBIGPUCy1iAAlQVHhWujvTm+CwLJYEiABEiABEiABEiCB5CVAozd5tWHNSIAESIAESIAESIAEYkSARm+MQDIbEiABEiABEiABEiCB5CVAozd5tWHNSIAESIAESIAESIAEYkSARm+MQDIbEiABEiABEiABEiCB5CUQsnuDvMqNHxIgARIgARIgARIgARLQAwHlJmVXKRskJ4Rv76BMZ1hdAtRCXd7RSqMW0eiom0Yt1OUdrTRqEY2OumnUQl3e0UqjFtHoqJsma6H80L1BSYNhEiABEiABEiABEiABXRKg0atLWdkoEiABEiABEiABEiABJQEavUoaDJMACZAACZAACZAACeiSAI1eXcrKRpEACZAACZAACZAACSgJ0OhV0mCYBEiABEiABEiABEhAlwQ0aPRegKduSXCXCXlVXvDPVA7XuY9RV2AKjS+og0eUdRPR6yqHaeB4wxLUeS7oUtDENEqE39OCpn01KDSXw9UbhB5WlUvwte1G6R2yRpko3HoEvkiHhf2KX2NB4AxcpdmKvmFCQd0pEH8s2DIPbRDohcd1EPtqCmEudaF3pEr3ulBq6p9XgvMF54qRUI09fjRacL4YO9+v8svxp4UGjd5JSC9qRKBrP4oEAFY72ru2IO+6b6Co+RRO2osgQIDVfhKB5iKkB1toRGreFnS122G1PAWn92UUpU/6KmcGj41CQPTU4/5NO7F/XQl2fRHpQBH+tu14YMOnKNjTCSnwFgpPV+CB2lb4Ix3OuJgSELt/h1d2tynyzMXS3OnQYOdXtIFBEhgtAflGyaPY1FCPdSW7EHGICmZ1Cd2HmrDbp8jXehdyzZwrFESuMDgaLThfXCHkUf58nGohhX0AhMUk69cvpXb7YglCmeTsCQxVMnBSslsFSSjaL3UpoiUpIPU4N0r32E9KIdFDv0y6kHa0kNGNoIecFNRkrmRznh5i3OOUbMJiyd7+5VBcEoe0pYUS5F8ld/XyUPbKZA2GtauFBmFfpsqa0mJgbrA5pZ5I7Tp/VKq2bgydTyIdl6RxutGC84W6Z1i0fqFDLTR8s2cSzLl3wepzoNl9dujKxjgduUtz4at7Fc0dSheGs3A3/xkLeIdriJVKIbHjPex1pCFjWspQiamzUbCsG3sPd/Ix+xCV2Id6j6GxdheqNlejrqkFHj+dGmIPmTlqn4CI3tYDqHX8Cpt/bkeTy8OnUAkSlfNFgsBHKFaPWmjY6AWM5rlYavVid/MHCh8tP7raPwVwONSg6v0AzR/l8FFVhBM7vlEX0HH4LTgEM6ZPnRhW1EU49r6HDtphYVxi9fUCPPt2oEp+XNtSheKFdyDj3sfR5BnRozFWBTMfEtAWAdGDfZX18MGHlqofY2G+BfeWNvEiUXUVOV+ojnzEAvWphaaNXgzc1d19CO6BxVO9H+AQFqHCCoVBJaLX3YKPFsyFWdstHvH0TN6E/ouQTDOmpRC+ujr1+b9L0kV43a/BbrMCLRVYuMqONt7xVVcKlpbcBIwzUdTshRTwwn3gRdgs8nXiWqza4eYdX1WV43yhKu6ohelTC41bIeEuDrJx2woUPIgFS3MBx1s4HHRxoGtD1HObiTonMBFC1vdQVPkavM6nYGl5BY2tCpcgnbeezSOBURMwCsj6/kOodP4XnGWZaKk9gNaBGyqjzoQHkrhmdFYAABrCSURBVAAJJCsBjRu94S4OZ+E+BMzLTuvz9x1wcaBrQwLPvxRMy7gZONGBLt5dTKAOctETIeStwUYbwlyCElytcVN8+NZxBhjk7RZpVCXfGWBMQ95jpbAhbM1I8tVUZzXifJE8gupTC80bvSEuDn96H4eQg+xUY7+/r+zi8J9wH6VrQ+I6Uv/d+PAKiGfQefwcrEvpchKOJr7f5YEsA5kZJiiWFca3SOZOAlokkGJCRmZG6AJcLbZDU3XmfJE8culTC+0bvRhwcXgN9sdfBebNRqp81vT7+8LxAkq3fMZdGxLYk4ILDjPfDd1lw+9F+4k53C9WdV386OrIROmidO7Tqzr7KcirdMt7Qg79ebcgL1UHw7DqLFUo0O9FR1YxFnFPdxVgDxXB+WKIRaJDetRCF6Nt3y4Of8Get7+OedmT+8+TSTAX3I8ioQ0tE7/LXRsS2XuM6ViyZRFaN2+Hy3cJELvherYWres3YAknlPgpI/rQdvA/0CYzlz+iD61ba9EybxksNLTix505a46A6GvDwYNtg2+JFH1HsPXnxzDvkdy+myiaa5GGK8z5InnE06MW4bsga2qD68HK970YQRi26fhpyWmbK1k19EKKwSbJt4O08qKQ4IsmEKyvXGdAiMD8ouQ9uk1aLsjpVslWf1TyauUtIVrSQnkCBbokZ5m1X5dZ0vLqVyVne8Rt+ZW/SvqwZvpF0pO88gpqQwv5xURlkhAcmwbGqdAX4wS8DqnMIvT1FWG5VP3rd6T28xoaoDQzRl1ei76zkvPFlffOy+UwPrUwyFiUlxUGgyH46E0Zx3BiCFCLxHCPVCq1iEQlMXHUIjHcI5VKLSJRSUwctUgM90ilUotIVBITF66FLtwbEoOSpZIACZAACZAACZAACWiFAI1erSjFepIACZAACZAACZAACYyZAI3eMaPjD0mABEiABEiABEiABLRCgEavVpRiPUmABEiABEiABEiABMZMgEbvmNHxhyRAAiRAAiRAAiRAAlohELJ7g7zKjR8SIAESIAESIAESIAES0AMB5SZlVykbJCeEb++gTGdYXQLUQl3e0UqjFtHoqJtGLdTlHa00ahGNjrpp1EJd3tFKoxbR6KibJmuh/NC9QUmDYRIgARIgARIgARIgAV0SoNGrS1nZKBIgARIgARIgARIgASUBGr1KGgyTAAmQAAmQAAmQAAnokgCNXl3KykaRAAmQAAmQAAmQAAkoCdDoVdJgmARIgARIgARIgARIQJcENGz0noGrNDu424S8Om/wr6AOHlHWKjzdhIK6Uwgm6VLKZGmUiF5XOUxKTQbDS1DnuZAsFdVpPXrhcR3EvppCmEtd6I3UStGH1q2F/RoVoLTpFPyRjmPcFRIYhRZyCb0ulJoUY5iB/eQKwfPnmiJwCb623Si9wxScx02FW/G2J+LIpalWaaOy42+M0rDROwV5la04374fNosQPL8EmxM9zUVID7ZKTj+MdvtiwFKG/e2n0Fw0ExpusDb6EM7C3eyAL1JtrXch1zwpUgrjYkLgAjx1j2JTQz3WlezCFxHzPIf3DxwB7n8JXukivEfvw+drf4TNrjMRj2bkWAmMRgs570voPtSE3coOw34yVuj8neYIiPC3bceK53uxcE8nJKkHru9+iEJLOZq6L2muNdqq8PgcozRuAxqRkr4AFXsaUGYR4KuqxYtt5/rPO7kz/RKrdt8K556nsCA9VVvno1Zr2/shjl1dAW9Agrzvc99fAD3Ojbhn6VyYNX7GJbcsk5BeZMcrOyvwjLXvQjC8vuInH6HntvuQI0wEMBFCzlIULgN2N38Q+a5weAb8PkoCl9cimJH/OP79hcl4uScw1F8GL9xHWRQPIwGtEhA9aCzfh28WLu0fk1Ixc8UT2Hb3u1j7/GGOSXHVdXyOUbowQYxCPsp/WYHlwhso2bATbX4Ros+JLeWf4ZGXy5AXnODjevYw834C4t9uxA9s+RCUZ5bowb7KT7AgdzrvtCf4TDHOuB2WNNng7f+IZ9B5/EasXzIHvCwcgKLWfxG9rQdQ6/gVNv/cjiaXh24maqFnOUlBQOx4D3sdaciYljJUH+PXMev2W+DbfQjuXjokDoFJREh/Y5TSNEkE0RiVaUTKzB9iy7Y1EFqqsWHbK6jf9AbMzz2NBcoJPkalMZuRCRiFGZiREnpayQNb07SFKKBrw8jgVE8R4fe4UFf2b+go3Yb1WdepXoNxX2DwYrAePvjQUvVjLMy34N7SJnj8nOjH/bkxLgCI8Hd14MSwtk7E1OlmCL4OdH5OF4dheNSM0OEYFWqdqAkz5mVNRNqCZ/Ba9Ry0lJVib85qrJjJe1cxx/yVM7yAjsOtuPXB7yBNR2fbV8aQVD+QF3nm4JqMfBRX/Ra/bz6KDhpa6itknImiZi+kgBfuAy/CZgFaqtZi1Q437/iqrwZLVJ2AESnTzMjEYew93Dl8kblgxvSpiqdSqtePBUKHY5TOzJCvwTTnW7DAB8fuN/E+J/LE91qxE4ebbkBB9uTE14U16CcgL/J09xlb9cuAqoWw/PQAunmDMTFniFFA1vcfQqXzv+Asy0RL7QG08rFuYrRgqaoSMKbfh1KbCY7Hq1F/qm/HBtHnxm+a2+DLNGNa2FNDVSvHwoYI6GiM0pXRK3a/jk2Nt+KXR2thkd0ceMdk6KRNUCjo2nCrBdmpujrVEkQzxsXKA1nhJrxgXwzfm2608yIxxoC/YnbGNOQ9VgobHGh2n/2KP+bhX41A+JaWBhhM5XDxYuOrYbzio6cgb+MeONb/HY/fci0MpkLUHvkDPm79BFYufL5iujHPQAdjlH4sEX8rasu78FDNAszMWYka2c2hZCO2uLqHPzaJ+ZnADCMT6HdtKJjNRVKRASVB7CSYc++CNQlqwioASDEhIzMjdGEPwZCAngmkpOPODQ3wyrv9eBuwfvYEHG9fgtJF6Vz4nIy6a3yM0ofRK3bDVfU6JpetQFbwcch1yFr9LOzLvaj4UQUOcL+/xHQdujYkhvtXKrVvMcknd2cjg48SvxK5uBzs96IjqxiL0rmfdVz4Dmba7+IzuK2ibHBtQR6fSA0SSkRA9L2Nx1e9hjtfs1GLRAgwmjI1PkZp3OiV3+TShJqVRWi2rEORcuFayjewqPBeCL7tWPith7C11cc7vqM5oWN4DF0bYggzJlldQnfTWpjuKEVDW19/kLf2e7byLMpL5nGhYUwYjz4T0deGgwfb4Ov3pRZ9R7D158cw75FcPhkZPUYeqQcCfg9c+2qw8v++jOsrf8HdZJJEU12OUVLYB5D3SNfAJ3BSslsFSa5v31+WZHOe7q94QOpxlknCYFr/MVa71B7QQNv6q6gZLSIi/VJqt9ukavdfI6ZqLVIbWkQ67xdL9vYv+3EHpPMn66XlwkCfmSUtr94vub0XNSWHPrSQpIDXIZVZ+scwYblU/et3pPbzGhqg5DfPaGW+0NQZPrbKalKLHqdkC45HVslmd2ru/B9JKW1ocbn5Qp9jlEEWTXlRYTAYgm8GUsYxnBgC1CIx3COVSi0iUUlMHLVIDPdIpVKLSFQSE0ctEsM9UqnUIhKVxMSFa6Fx94bEQGSpJEACJEACJEACJEAC2iJAo1dberG2JEACJEACJEACJEACYyBAo3cM0PgTEiABEiABEiABEiABbRGg0astvVhbEiABEiABEiABEiCBMRCg0TsGaPwJCZAACZAACZAACZCAtgiE7N4gr3LjhwRIgARIgARIgARIgAT0QEC5SdlVygbJCeHbOyjTGVaXALVQl3e00qhFNDrqplELdXlHK41aRKOjbhq1UJd3tNKoRTQ66qbJWig/dG9Q0mCYBEiABEiABEiABEhAlwRo9OpSVjaKBEiABEiABEiABEhASYBGr5IGwyRAAiRAAiRAAiRAArokQKNXl7KyUSRAAiRAAiRAAiRAAkoCNHqVNBgmARIgARIgARIgARLQJQENG70X4KlbEtxtQl6dN/BnKnWht18q0VOHAkWawbAEdZ4LuhQy4Y3ye+Bq2oOawgKUus5EqE4vPK6D2FdTCLNCowgHMipuBC6hu2ktTAV18IhxK4QZDxIYzTl/Cb623Si9wwSDIROFW4/AR20GCcYvoORugKlwK972DMwc8SuVOZNA8hIQ0esqhynEZhqwrfRjO2nY6J2E9KJGBLyHUbt8FoAs2Jyn4a3MQ2r/WWVML0JzjxM2wQpb/VF4A40oSp+UvOecVmsmnkLd/Y+jYX8FSnb9JUIr5AuUR7GpoR7rSnbhiwhHMCr+BMTu1/HE2u3wxb8oloDRnPMi/G3b8cCGT1GwpxNS4C0Unq7AA7Wt8JNgHAn0cV/xfC8WytylHri++yEKLeVo6r4Ux3KZNQkkM4GzcDc7Is8P1ruQa9aH7aRho7fv5DEKt+PR7XZUW7yoqvxt2B2sS+g+1IyebS+iojAHguZbm6QdxjgTRa83YueTj8IasYryBYodr+yswDNWIeIRjIwzAX8rast/hyl3yheI/MSfwCjOedGDxvJ9yNm4BnnCRMCYhrzH1iOntgaNfCIVP4n6uX+zcClyZO5IxcwVT2Db3e9i7fOHB58Uxq8CzJkEkpBA74c4dnUFvAEJ8jsb+v4C6HFuxD1L58KsE/tJH81IycaPN66A4NiKygOfYeDpoHxna7PjNmycfxP00dAk7CiskgYInEPbjj3AuodRMPVqDdR3fFRR7HgPex1pyJiWMtTg1NkoWNaNvYc7B8exoUSGYkEgInfj1zHr9lvg230I7t6BGSQWpTEPEtAGAfFvN+IHtvzQm4OiB/sqP8GC3Om6saF0YgsakWpZhW1FQN3aahyQH1GJn+HA5qOwbvwe0nTSSm10HdYyuQjIj3J34Xk8gNVZk5OrauO6NhfQcfgtOAQzpk+V7zYqPxfh2PseOmh7KaHEKCzC39WBE8Nym4ip080QfB3o/JwuDsPwMEL3BIzCDMxICTWW5AvEpmkLUaAT1wZZxNAWallW402Y//QmFGE71j5/CB8f+AUc1ocxPy18QtFyI1l3EviKBPxu7HgeWLc6G4r7iV8xEx4eewJ+dLV/CmSaMS1sool9WcxxiIARKdPMyMThyHfTI16EDP2aIRIYPwTkC/NW3Prgd3R141A/Rq9swaf9K0qfWQxf1T249YUMrKdbw/jpn2xpBALn0PaSCzdvWY0sGlYR+DBqPBIwpt+HUpsJjserUX+qb8cG0efGb5rb4ONFyHg8JdjmSATEThxuugEF2fp6QqgroxeYhPRFq2ETBFh15Hgd6XxkHAlEJyC7NbyK/Tf9kE87ooNKUGoKpmXcDJzoQJeffgzqijAFeRv3wLH+73j8lmthMBWi9sgf8HHrJ5w31BWiv7QzcJVmD247Gtx+1FQOF32rE6LGQKFB14ZbLchO1ZeZqK/WDKjF/yQw7gmcRWvjr1CxcDomDO67eD3yq9oARzEyJphQUHeKi6USdp5Mgjn3ruG7nYhn0Hn8HI2veOuSko47NzTAK69S9zZg/ewJON6+BKWL0nXk8xdviMxfvwT6XRsKZg9uAauXttLo1YuSbAcJhBCYgrxKt2LrGXkLmtNw2rIAqx3tAS+ai2Zygg9hpu4Xo3kulma+i2b32aGC/V60n5iDpTpaLT3UuOQMib638fiq13Dnazbk6eyuVnISD69VhLHKu4VahGNS87tOXRtkhLo1ei+d7eVLENTsJCyLBEjgqxEwpmPJlkVo3bwdLp+840w3XM/WonX9BizhS3S+GsuxHC2/RXJfDVb+35dxfeUvsD7rurHkwt+QgO4I6NW1QRZKR0Zvv1/Qtfmo8vnQUnIbrjFkj/BKXN2dowluUB/7CRnFcKANVfnXwxDyqtv+1xtOuAXFDh98Vfm4lq+ETrBmLD6+BEZzzhuRkrUGeyqnoCHrahgmFKE54wnsWZ/DnTbiKU6vC6UmAwzXPILm3jn42fGdeDRH0NNkGE96zFv3BGTXhnZYlszRnWuDLJ1Bkl+7ofjITuRhUYpUBtUkQC3UpB29LGoRnY+aqdRCTdrRy6IW0fmomUot1KQdvSxqEZ2PmqnhWujoTq+aGFkWCZAACZAACZAACZCAlgjQ6NWSWqwrCZAACZAACZAACZDAmAjQ6B0TNv6IBEiABEiABEiABEhASwRo9GpJLdaVBEiABEiABEiABEhgTARo9I4JG39EAiRAAiRAAiRAAiSgJQIhuzfIq9z4IQESIAESIAESIAESIAE9EFDuSHaVskFyQvj2Dsp0htUlQC3U5R2tNGoRjY66adRCXd7RSqMW0eiom0Yt1OUdrTRqEY2OummyFsoP3RuUNBgmARIgARIgARIgARLQJQEavbqUlY0iARIgARIgARIgARJQEqDRq6TBMAmQAAmQAAmQAAmQgC4J0OjVpaxsFAmQAAmQAAmQAAmQgJIAjV4lDYZJgARIgARIgARIgAR0SUAHRq+IXlc5TAZDcOcJeaXesD9TMepO9epSwORolAi/pwVN+2pQaC6Hq1cMq5ac3oyawsx+bQpQ2tAKX/hhYb/i19gSEH1tOChrZDLAYIqkU2zLY2698LgOYl9NIcylLkQegS7B17YbpXeYYDBkonDrEfaLuJw4o9ECQK8LpXL/GJxHlqDOcyEuNWKmMoFo8zfZ8xyJPQEdGL2X8Pmf/gElR70ISBLkbdf6/i6ia/8aCJiFom1PYMXM1NjTY45BAqKnHvdv2on960qw64vhUMTut/DSG8B92/8ASboI79H78HnZfDxQ2wr/8MMZE3MCl+Br3Y6VWSvQ1HkjClt6IHm3IC9VB90/5qxileEFeOoexaaGeqwr2YUI3SI44fvbtuOBDZ+iYE8npMBbKDxdwX4RKwkG8xmNFvLBl9B9qAm7fYM/BKx3Idc8SRHBYGwJnIW72QEl8sH8yX4QBQMxJCCFfQDZZtTS57T0zv7fSz0hVQ5I50/WS8sFSELRfqkrEJKomS/a0uJLqd2+WIJQJjl7lMC/lDre+X2YBiMdm7zSaEsLJceAdN5dK1mE5VLtUa+kVEZ5lJbCmtIicFKyWwVJsDnDxihJkoJpcyWb8/QQ/h6nZBMWS/b2L4fikjikGy1kxuePStXWjWHjVxLDD6uaprQYqHvPO1L1RofkDRmYAlKPc6N0j/2kZscrTWoxoInO/odroYNbPan4xrfTkaK8EPC7seMnZdiVUYvXnpuPNB20Utk8bYUnYYblX8I0mIip080QtNUQbdZW7gsbXsHN257GT3MEsCskj4xix3vY60hDxjTF6JU6GwXLurH3cCfo/aOmViJ6Ww+g1vErbP65HU0uD59CqYBf/NuN+IEtH4JyYBI92Ff5CRbkTud4pYIG460I5amm0bZPxA3CZEXnOIe2HU+jpGUOqmtWIitFB03UqDKXq/bX7s5GBvW5HKYrSL8AT2MNSpCP28VfY2XQVzEThTXN8PhpUl0B2Bj89AI6Dr8Fh2DG9KkTw/K7CMfe99BBicK4xPFr0NCqhw8+tFT9GAvzLbi3tIn9JI7I5ayNwgzMCJsD5IvBpmkLUUC3kjjTH5/Z68wivASf6zlsKPkMy+3PYnXWdeNT1aRvtezH1Y3VD+eF3QFO+oprq4JiJw7vPQZLziz88+3r0OAN4PzJDUDtSqza4eadrISq6UdX+6dAphnTwib9hFZrvBZunImiZi+kgBfuAy/CZgFaqtayn6h+PsgXg6249cHvcG5Qnf34KFBXRq/Y/Toe/9FTaC/ahC0rZoW6PIwPPTXQShH+tj1ouH4NL0rirZbfi/YT1yGn4G5kCfLdRCNSZi7Fz57JRUtJDRq5Kj3eCjB/rREwCsj6/kOodP4XnGWZaKk9gNZhu9ForVEaqq98od50AwqyJ2uo0qyqlgjox+gVP8OBJ55EHdZg29Pf41Visp6FfjdeavxHlK3O5kVJnDUSP+/E8WHLoifBnHsXrPgU7V3cOyPOEkTJPgXTMm4GTnSgi64mUTglKMmYhrzHSmGDA83uswmqxPgrNujacKsF2dxZJkHin4GrNFuxZZ/+trfUidF7Dm21a7CwzoSyl8swPy3cR+4C/P6/J+gkYrGDBMTPcPClP+LujQ9iJh/pDmKJV8A4dTq+KXhxvPNMhEVRN4cuoIpXJZjvCAQGLj7CksUz6Dx+Dtalc2HWyegc1kLtfE0xISMzg/1ENcX6XRsKZoMbjKoGfdwVpINhVX5cvhMbSo7BUr0Z5XlpikVtfXqKnnfh9NLoTejZLXbD9dybuOb+HwwZvP4P0VB3ZIRN+xNaW30UHtwJwIQTRz5WvPBAhL+rAye4B2bCNTaa52Jp5ruhdxKDLilzsJQr1xOuD/xedGQVY1E69+lVRQy6NqiCOXohU5BX6Va870DS3Z7u2jd6g1syVaPFUoKaCI/MRd8RPFfpxjXDVkhHl56pMSTgP4WmsiLkr/8J8k1XDz06ucaKPfgnujnEEHVoVlNgWVeOu998EuX1HwYXrom+38Pe8BnWb1mAdO33/tDmau2bMR1LtixC6+btcPkuAfKF4bO1aF2/AUtoaKmqZvBthQfbBi8O5Xlj68+PYd4jubzrqJISdG1QCfR4LyZ8H+LwjXzD05Pr+2nJacuS5DpH/bPapfaQza+TqxUj1UYzWgQ31FdqIEjWgY3FA53S/qJZI+jDTfhH0j528QHpfPtbUvXyfg0sNqnere2XVGijX8gb7JdJQsjYFOl8vyh5j24LvkgHsEq2+qNhG/XH7kyIR0560SLgdUhlFqFvnBKWS9W/fkdqP6+tSUMbWox0FsovLLJJ1e6/jnSApuK1rYWmUF+2suFaGORfKA1/+Z3jYVHKZIZVJEAtVIR9maKoxWUAqZhMLVSEfZmiqMVlAKmYTC1UhH2ZoqjFZQCpmByuBR9wqgifRZEACZAACZAACZAACSSGAI3exHBnqSRAAiRAAiRAAiRAAioSoNGrImwWRQIkQAIkQAIkQAIkkBgCNHoTw52lkgAJkAAJkAAJkAAJqEiARq+KsFkUCZAACZAACZAACZBAYgiE7N4gr3LjhwRIgARIgARIgARIgAT0QEC5I9lVygYpE5TxDJMACZAACZAACZAACZCAlgnQvUHL6rHuJEACJEACJEACJEACoyJAo3dUmHgQCZAACZAACZAACZCAlgn8f9Ta7q1glDFjAAAAAElFTkSuQmCC"></p>
<p style="text-align: left;">Pauline wants to visit each town and needs to start and finish in the same town.</p>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Draw a graph<em> G</em> to represent this floorplan where the rooms are represented by the vertices and an edge represents a door between two rooms.</p>
<div class="marks">[2]</div>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain why the graph <em>G</em> has an Eulerian trail but not an Eulerian circuit.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain the consequences of having an Eulerian trail but not an Eulerian circuit, for Pauline’s visit to the ground floor of the museum.</p>
<div class="marks">[2]</div>
<div class="question_part_label">b.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Write down a Hamiltonian cycle for the graph <em>G</em>.</p>
<div class="marks">[2]</div>
<div class="question_part_label">c.i.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Explain the consequences of having a Hamiltonian cycle for Pauline’s visit to the ground floor of the museum.</p>
<div class="marks">[1]</div>
<div class="question_part_label">c.ii.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>Use the nearest-neighbour algorithm to determine a possible route and an upper bound for the length of her route starting in town Z.</p>
<div class="marks">[2]</div>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px; padding-right: 20px;">
<p>By removing Z, use the deleted vertex algorithm to determine a lower bound for the length of her route.</p>
<div class="marks">[6]</div>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Markscheme</h2>
<div class="question" style="padding-left: 20px;">
<p><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOoAAADGCAYAAADc+hwDAAAgAElEQVR4Ae3dB9g9RXU/8NUUJRojmiIxiVGxJJqYaBAhIaKAKHZUFKzB2AgoitGoicTuo4INsBdsWALY0AAKhCSCDbumWKKJXWNJr/6fz+T/fV3W+966d3fv+9t5nr27d3d25syZc+aUOTN7me9973vfq8Y0YmDEwKAxcNlBQzcCN2JgxEDBwA9Pw8MobKdhZ75ncHjZy162+t///d/qMpe5TJX///mf/1n98A//IPo9D969550xbT4GVu3Hy0xTfUMwm4+m/lsQBsWwUp1569B57pn8q3Zuvdzxul8MrNqXo+rbQf9hOsd//Md/bDHgf//3f5eadWDz8MzhnTGNGICBH9S9RrysBQOY7l/+5V+qiy++uHr3u99d/fu///tEZrzGNa5RPfzhD68ud7nLbTH1WgAaC90oDIyM2lF3kZpXutKVqlvd6lbV5z73ueqkk04qx81vfvPCkBj5Ax/4QPWiF71oS5JSgcc0YgAGRkbtgA6a9glpGUeSZ3E07b333tVXv/rVImmB9T//8z/VD/3QD3UA4VjF0DEwMuqae6jJpPn/X//1X1tM6B6G/Ld/+7fqDne4w5bNGsfTmkEci98ADIy6VYedFOkZKRmHEcn5ta99rfr0pz+9Zbe6N6YRA8HAKFGDiTWdJ3luMSz780tf+lL1N3/zN8XJ9Jd/+ZfVNa95zepXfuVXCiSeyzfp/TWBOhY7YAyMjNpD52A+jPjxj3+8+vKXv1z96I/+aPW+972v+oVf+IUeoBmr3AQMjIzacS9hUI4kc6q3uc1tqv32269ITarvF7/4xY6hGavbFAyMjNpxT8X25PmVSFfHT/7kT1ZXuMIVOoZmrG5TMDAy6pp7ChOyNaV4cZ15faU4llz/yI/8yFZe/707phEDMDB6fddMB2FS1WS+1DUmpAaHkSNp1wzOWPyGYmBk1DV3HEaNJHUtdPATn/hEmYbh6f3nf/7nco1pragZ04iBSRgYV89MwkqL98yVUm8xK2fRRRddVJhTFZxKP/ETP1EJI2Sf8v6OaWdioK5ZLdPCkVGXwdoK70TFxbikaGxV1xjaWdKxjtFOXQHZA3p1VUYdnUkdd2YYUbWYsM6cI1N23BkbVN3IqB13FkZN6KBlbyTrj/3YjxUoEqjfMUhjdRuAgdGZ1HEnUX2//e1vV29729uqww8/vAThv+ENb6j+8R//ccvp1DFIY3UbgIHRRm25k2J7Ro11do8UdX7/+99fPetZz6o+9alPlWVspCj7RcCDSKUjjjii+sVf/MUCVWxU78rnSLktgz0Wt2YMrGqjjozacgeRmDqFiosxw6S8vSeffHL13ve+t/rVX/3VkudjH/tYdcUrXrF68IMfXO5/8IMfLGrw/vvvX93znvesbnCDGxTmVAZbFpM21eORcVvuwDUVNzLqmhC7bLFhTozKBsWMdm14z3veU/3sz/5sUXdvectbFubEZGJ8jznmmOrII4+sPvShD1VvfOMbq/POO6+8azeIu971rtVNb3rTwviYVfTSmDYPA6sy6uhMarnPI1Ex3Ute8pLqwgsvLHOlRx11VHXve9+7qLhnnHFG2cnhcY97XPXSl760+od/+Icieffaa6/qN37jNwrzYu43v/nN1Vvf+tbK/fvf//7Vb/7mbxYJXAcZ845p52NgVH0X7GNS0OgYdTQS1Fn667/+6+qUU06pzj///MJU97jHPYrd+dM//dPFJiVpH/3oR1eXXHJJ9epXv7r64z/+4+pb3/pW9YpXvKL68R//8S2VWT22ZTn77LOrl7/85SVYwsZnd7nLXYpavNtuuxV1OGq2/MqWAmP5M/4MAgOrStSRURfsRkwQRnCWSFG7M5x66qnVueeeW4IYqKzsTMwlqMFqmeQ77LDDKsejHvWo6tnPfnZ1+umnV2eddVaRtrFt07HqEGZIHSahDQQ/9VM/Vd3+9rcvA8DVrna1wqBxNHnfOyStwSPlLNjMMXvLGFi1H0bVd8kO4YnFeH//939fvepVr6qos5jjtre9bbE37dYQCXf5y1++MA0GOvPMM4sH+E53ulPJf53rXKfYo3/3d39X1aVuBgH1CC+U/9a3vnUlPviVr3xlkbKvf/3rC8Pe/e53r653veuV+sKg3kMcqxLIkugZX2sZA6NEXRChpCMGNe+JYTh/bEqGiR74wAdWGC9SzdmBWbz3T//0T9Xd7na3spPDC1/4wiL5vv71r5e5VHOqJCwGjVod0NxTBuZzYMa/+qu/Ksx6wQUXFEbfd999qwc96EHVL/3SLxWbOIyewSJljed+MLDqgDlK1Ea/IXBHCBzTYEyqJWb77ne/WxxAHD2YlQr6u7/7u9W1rnWt8k4YU8ekc8J4tlshgTGUZxiOFDVvyjuc79Gk7oCWcsAQiXnd6163espTnlJh9Ne97nUV6Xqve92ruv71r18cTyS797LGNcyeMsHknvLGNHwMjBK10UdhVLcRs0PCoGxJTMHJY64TY9zkJjcp9iemwMiYyXWYC5NjPHbmIx7xiOqTn/xkUX8FOChbvuOPP77YoDy8V77ylS/1fpNp6/AFRve+8Y1vlHLZupbRYWTS+853vnO1++67FxgCS2Dzfv26NHT8WQsGVsXzGELY6BYIxUBUTAwg3I+04hx65jOfWSQgtfU5z3lOmUqJBMUEkV7KyOG5cj772c+WqCT79oZJSTPPSGP1mFOdJynTuw51OnMwPeQhDymqODh5hUVAHXjggWVHfjawuiSSe1XCmQfOMU97GBhV321wiZj/5E/+pEyhmOe80Y1uVP3RH/1RdbOb3axIzUhODIoBQvg5p9gwrO/NYH5hgmHuPOMIUp+tQ6muuZ8y6ucwfiR9/RmJjnE5ng455JAyBWRqR0SU+VrqMFvYlqSR5vX3x+vhYmCXY9S6+hepSSIhXEzA4UN95MX1LRjOGdLT4m7eW3nqqfkfk2HcMJLzd77znRKE/8u//MvVz/3cz5XXI93kN4VjDtX2oZgp9jC4muXX3wscymjmw7B2OBRAwfF02mmnFdX4LW95S4l0uu9971vts88+hbFTpvpcO49pWBjYJW1UxIi4w6iYlzQyVynwQDCCOFvEfPDBB5fABXkwkGNaCqOG+G0Lam7VF9qe/vSnFxXa+4FBvcpm77r3mte8ZkulxXwpZ1qd055FzQXX5z//+aIamyL6yle+UhiVSk/6aldU97RV3c0BYFV4psG6k5/B/yppl2PUEBpJR3LYw8iKluc///nVRz7ykeKBFU3EEZOtUZzD1Ih5WmoyKqLn5f3CF75QmJBjB1Oo2zPl+v+0pz2tDBIimvbYY4/CIMpatYOVH5jUp16eYhoD25sX2pwv+1aI4s/8zM+UwQGDjpJ1Wk8v9mzVfpwuHhaDZSNyI9aouX/+539e7DerVkT4PPKRj6zueMc7bnlJEWvya1xTuszTYAxKheZ9vcpVrlKYRjl1aaUOdiPG+MxnPlPU48A4Tx3T8oRJle1QF2cWxhR7nIinP/iDPyg4uN3tblfsWLv2gyEDW+oYmTeY6Pa8IxkVcSGyECmUIlAM4p6AeUHvGNQ3S4877riikrpGiPLkiKo7L5NmikZ9EocUqWYAAFdTIgcmtrBn7Mnf/u3f3oIdHKukJmOlPcrUXmqvqaYPf/jD1Zve9KYSRGEaik1O9WcCgBscGWDgVvK/iZcmY68C+/ju9zGw4xg1hBLCQlSYBsFiUOF+PLBUUKF34nE5eOTBKCHKZRkEI6jT2Xdl3vWudxVPMUdSnUnSBalP4ANJx6FUhyX51nXWTiGKv/Vbv1VU349+9KNlrvicc84p0pY6DE+W2smrDcEt2Ov4XheMY7k78EPGIfyM+pw51E8B8ySFhdrUUIu1MUfs0DCmcw4EEkKcl1hSLycOosesbNSmZEt5kUjgEqHE4UMqJ3/gSv62z5Hw4FbXr/3ar5WF7ccee2zROt75zndWmNb0lKV2QhV5v+vweU871g1r223fpPJ2nDOJNKJqYsC//du/rV72speVpWIYlofzPve5T2GIEBcCDZFhyjBOiG5RRlW3BA524Oc+97nqta99bXX1q1+9wBUCD5GEQeQ3DSSYwhpWTp3AmLzrOoO52e7AZaDhtYZHn4k0lXS/+92vYsuaUpK8q13gXRRf62rT0MoNPS0L18YzKgKXIAJxIRSeTKF+4nETMI+4ssKkjqxJ6mj9+aLXpCFYhAqacuFBFmwfBm12WAgb7BdffHGR9NaokvpS8js7kn9RuObN3ywfE7vHO/6nf/qnxeYGp2gqCxGYDnauCKyYNn3iOvDPW/9OzbcqHjbORkU0CCAMoWNDXCKIMCc1F7HY8gSD2qMII2DK5F0XQagHU7JNnQXtp5NyrtcdwpaXHSsPJhdq6DoMXn+ny+swG9WcRkKSWlxgbayF7wZEbWTHcjzVpXNw0SW8O7WujZOoiBezYUREjGFF/iAYwQIii4T5UTsxKHtKnjhB1t2RiFMA/qGHHlps4Be/+MXFSQUOadJA4R3J2YJyeTGCeN0wt3PaXjJ39AMmB/zBeQYW1Zt3ttTPGlkS18BIizDVxPSQt++BpiM0zawm/Tgz4zYZNlKiIhwNt2LE9IfwOLbgLW5xi+Lw2HvvvbcYE3FxmOSdJqOsisAmXg0Ktk8RBP/Qhz60MBsYHOpq1uc/mBC0M/Wcamm1jl0huib0JnypP/CTmO7B541vfOPiZDL3qx8EUNAkDJBUfqpxNhdv4mn8vxgGFpaoiEknffOb3yxqzlWvetUtz6lnRtFVkjLqxKIuxG+ERiwSqckbKdwvAfMkqCkEUqjLBF6HhIDtPGhXQQOHUD0fgZqVwqzaZ9ARashDzQ6MDS1P8s0qr8vn2o55weYjWOxYG4pbLUSVF+FlIQIPu76U6jTi2n240/76sy7bse664GeVtDBXpWOsxqBuxu4LslcBxrsh/DphYlL3SZm3v/3tJXLGShZrNxG1uVHB55lqWBWGRd4HV4gLDkhS87WC66PuLlKe1TM81MrIwLTI+13n1eYMJj//8z9fNBrrap/4xCcW5rXkjr0tRJOTT5vioAreQsT+p99z7ro9Q61vKUZFSGJSqXi8qiHWtghLecoK87P51GV0Fubn2YknnlimDLJsbBmmaKNTSIK0X3lW3hhQBBAsM3Bc+9rXLuoiRlXu0FPUYOdIVtd2/Bfp9LznPa+o83ZmFJ31+Mc/vjCsvqUphWlDO9pcP4be/q7gW9hGhUQxslRM24e4PuiggwpTZYRcFXidGEZVvtFYXVSpJzzhCcXzKJoGQRh5wZRRedW6F31f3YiNVDHPiFGF33GoeLZo0i7v8vyGeBcto8v8aaMzzUffsa31hzNcGLQ4niwEeMc73lH2KnaP48w5Wll8CXX49fGYqmqqREUojnQGgiRB2SFUTkTFRe95Pd8iiNWx9VFVOaJ67Cwvooe9R0I95jGPKV5dnWuqQOdmYOiLSbVT3YgJDiyPs02Lhdvgm4fIAjs8SN5ja7O9LUVzXx5H+mER/K47b9qfvnB21O9jQKbJU5/61LLMzjQPjUH/CkChLdHSQm/eTXnar93ueb6rpqmMimgcdQKxH4+d9vbcc88iSX3sSAQQRIbYpiFTWc1DHWFQgfKC5HUib6KNw9g8wtey94+6hpK0RbsNNhZlm/wXbhdCmwdOZWhTjhve8IZlQOSQ2vSUNuXMq82/gDmPPvrosuTu937v98p0FlXZZuRoAU7rOKQmK2NXTVMZNQwFYRBHQoj7zA53JAdpJ8ggz2chMmXmbCTlKaXqPexhDyuMaUJd53H5Y1oufjB4Bwyuh9JpiIrEsDG2da1WolhPOm/SJimEDI9ifqmR4n43PaVdOacPOQJt9kYdtrcTNZn9av5ZKCXNBC7g1yAYGtx0fCwL/1QbFaKkIJn73QZcvHuQZwc+IyRGNT0C2bNSCDP5uPFN7nNO6QyRRNRbK1rUH6YEg5Rz3u/7DD64YA649smJwKyts+Ct5wmeSWXrY61j/Z3f+Z2+m7hS/c3269NoadpuqV32ePqLv/iLwrgveMELyiBtYzb4jL0/jymxErADfnkqowbJCBGSqCZGOg6dII29aErCvKZJbkSqAxz1pAwdJBklvXPqqaeWjiE9sj+uBctSk4DLzW0ie/Ksq3PaFxgFXliA/eu//utlc2240cbgbxpczTz+w4ftPjEqnwBfgJSBa1p5Q38WT3i93a4N8gcccEAJWqGZWMhgKo4QEPGEtgRY8O4H/3U8K8N99LcT01RGjUTVcOop6Wd1hwRhnD4CH8R5ZvokDAxx3k8ZkMjOQNQYFNMLO7NwmR3K5vXupiFauzCUpXTsaHjRdseySZm0FTYv9RfTYl7Mv2n4mYWD0Evy+W/TNc4ng7mwUJ50K3gMhDQuIaLMoQz+OcPbulOzX5t1znq+LHxTGTVAqJxqCnkQRDK655rqwsUudIydSU0JMWFS+fzHoObS3va2t5U9bKk0CJs9Jk8cSs2OCwzLNnDd7xl8ROJQVU1FRGvQpmVS2ivAXVSTaQ1BEFLKXqbcob7TxJPBCA047OVkc3KORfQlyIbvwsDFPDIvS6MjpZUT3K2zrbPqmPV8Wdjm0hMEHLAjrZwwsgMmjIVQRZ44U1cg2nNMaqTzX2A6l7zwOHG4wuNM7/AeU3lSFob2bv1YtmFdvceJxPPto8MYS7u1WWoS4Twwabv3MKfyeNndy26C85SxSXnqfe06gzxGRRf+c87ZFgbdYFzPnvzkJxdGFVBB64Bz9LbupJ760ayv/sx1W2mqRDWXJ2FABCP4gFczagckYmKSFIGyU/MNTxt5QShg7QPEO4xh7TWrA0LE9c5pq1HrLEc7JfBjHrYpswBetDeEtiwMypAMYOJjTVEZBOFM3auWvyxc63ovdNAs3/3mM4vpRafRxkhYswKkLPrk4yAMSFsSFtPGHg7e0GLupT70t0jiTPVhMLMfeILmY9qQL0H5ZjHMf3OIEUptpalB+ZaPST6GxKEBcSQqRpU08l//9V/LAQGARGhW/vsforNb+0knnVQQK9Dc/XTCoogqFff8o+PBr9NMJwj7o9Zr16qLAlI25hQviyBE8xj4dhqTLtONkVLwhBkxCwHAYwz/BkyL2W0po4/QYWgtZ/XmelH6U793hbDy11jmZ18pg3YGAQOHT4yI2AsPpL5l2uydqRI1RGeqBFJUamSXIApgDozrGWDqDU+jOIo0hORF1EkhyvzfhLM2pp3WYRrMjPJwVW/7sm1J+XBD/eVMEZqYr5GHGJYtfye8B88GLTTHE2yQ5MyzzI6TkrTFqLZDtaMjIeMdOJXg2PvOiybvhBeUR/PJf/TunvjzzAOHURetp5l/qo2qEodGkaSSBqeBAUwe9/zPcwAjKs+sT3S2JaV8Dvkcm5bS2dqKIIycnGzB06rtgRsdD99CCXmRrU8NYa5a/qa/Dz9wjXacJWcmlwUblhaKeLLXk/BTzErq2XQ89Loq3RFWjqi7oWd9RBMyMNj+1f+20tSSVFQ/MF4qD2HmOWAB736uAeka0QmoFx4YZIXg22pIl+WAnXbw3ve+t9jcmFXnBzerwhICpH1QeeFN+XC5qyc4Dn2FBuHEPf85nnxQmr/ksY99bJkCFGMsqMJySNqJvPoQLTowF/y6DhPL49gueb8+pyuv9w2q/DaBabv3F70/VfVdtLBJ+TXcCGNekO5OJRB5o2FByqT3hnovnWky3jwwG9UApeOmdeyy7SGt2WE6nxc4TLxseTvxvTreo/lpp6gugRKcoPwk7EpeYn1mGZ7pH++GFp31b+7lPA1nAjKYQAYQNMC5SIKjbe+3ldbOqAAFsPlSziYjWhi1rUZ0WY7O4Fy76KKLimrK/qaqYtZ1JCGaOp/X3Jz1mC6NgSYz5H/6w9kWPea4rdihGpv3NtXDKyuAgp1LW9S3BsK6AEl5l671+/+ouDQfjOobt6brSOi203qoqwalRjsQHMPbN0BJCQgwem2ahAAvW9uKIZPu1J+ovDo61zUUrHTJZOCIs5LGADem7TFQpynX6Q/XDhFN7H4bsGWKxfwsJja1I3CH9iflne1r+78npoPQcyQqUwWdt00HU23UWUDO8zwAmxMURYLgMCgpBBmbkHS4ZMDhQOBdtKG22FQjdtqY86ptghdlGRRoIvBmcIiUWLX8nfR+BEHaVB/44TC4hLswrui5Jz3pSSU0keOJ8PDlBOqwyDmefOWiUbQqKcc9/0MP7ruX/+rgbcaspGps38C2ynntjAo4CLMJGhWByhgGbYuwV0HArHd1Qjpfp5CkPlVhjkyb1p14M9VjIT3CGdNiGMjMgz50jfZyEB52iiRd2a82zfNVO8s4LbWzWgyzYU59773QQmjYOYzqTJrKz24VNttW6oRRNRKSLKgW2C/iCdFtAuHVOwLSTazrECs6tGndSV1UKxKVNB/TYhiIxIPHXOtT1w5MZSAUN0yaYljakq/9CXltJu9gVj4DiZMPcyqT4EHTQhrZwmYD2kprt1GDII1DcLb4JJHYWxmd2mrMOsrRMZKO4LG2ooXdyIngXheJOmUin4q21157dVHljqmj3kdhJjQp6VteYj4AzzAcO1UfYzgrwyKRPfeecFFOKTQsZQNyZclDbTZtx+OcekrGFX/WzqiAdxi5LDjXcHZqGGBF+Nf+OmQ7tMF8pjhOi+TjdFg7AFV1KUecaS7wxP4C15i2x0CdzsJMdZyhSzRJxXXfgHjBBReUe8Gx9xzwjpnZuBapYOam+aYMsxs89PW6t4dwviedMKoGQghVwMJwq02kIG4+UPvJBfFgJ/3t4mA5m/WSXWkDHBQGOB1vPtXcbd3T3A9Wdk6t+hfDOaNLDEjzY6JhwjqNyqM/hMxibv+byTskdNupExsVUWuAxokb5pBp0yPWNlLq5RlkwE3tJFEFYPvgMPi7SqQ3p5JVSHCJeDYFf13haNV62Jr2bpI4mDAkHOv/MCvGhH/qciSpe/VDXvQin6Ot1AmjZsTSAGtQ2XocSmlsW41ZRzk6jES1E6LOFIqmY7TF/XUnuAOD5VRGfBJV/ZuAu3Xjpo3yMaKDymtTvaOOOqo4PS2y4DDCeFKY0X+4z//m2XPHRjJqgEZw1EbEZg/cTUg6whaWYjhNmJvgxqCT7JN1tCejMnWM1xcxISwpRLSOendqmcFdztpJU+LltUTOutYMzvAbISO//+ghqX6de5i4PohOypO8i5w7kah1gEzgi1mlxtWRVc8zpGswGlTYLELRqKFsxDDQumGlfuls+wWxU238hRDA1RUM625jl+XDHYYz2MKtQdjX1EnQY489tgSXgAfO12FrLtvWzhnVanhSyeoTiBp6AiN3veggaxsxSAaYtkbLaTjAjAiLXcwZZ8DIAv0uVO9psG3is7pUxLRW1AjCsRdTYnb1qz6uB/j33dbOGRVyzEGyUwUxDz2xC+0ySCUyEQ5+h87sglHhB3EhHAEj4KGOYdKu6h96Hy0CXwZZA6DoIQvzhYLyPURDgVcChU9iKKkXRjVyQYLP8CHCHEMgPLBgBGfbzIhEwhQ+yutePTX/15+1dR3iYTdZ2GD7FwOcwWJM82FAP2HQaCC0JOF9opDs2M+BBL/yoEH5qMLyoQWpb3z30ts8vxj105/+dEEOREJQF4Q/q2vBoVN0EKeX/YowiMGljwQniAjD2poFfOxUaQj46gMnq9QZiWrzMfTnMyr6Fo6D0/r1KnW1+W4vjGoC3woDKmVGrKEwKuLXmTrLXsbiNu2JxEZNJ7fZAbPKghf1OkTEgCtb2sx6d3w+GQO20DEdI/g+G5Cx+yWDNFyHDiaX0P3dXhiVumFeUExk1JHumz65Rp2EOcR02gFQgMa+++5bOrAP9SdS05m3XJyxOFMDXB/wTMba5tzl5bV7oJUzlrZxGMFtHEf6H15FHw1pEUQvjEoqkA4CmO34gFkdGKTrpM76oZOomZY4kVyYlGOhrwEFbOAJXOZTRXYxHer4Shu6xt/Q68OEDgzI5vRRbFFmviRHs0OL9UgieQ2CND6Mqt/zfh3fXbe7c0aFMMmKEAjhxUSEkJBnXSNBffUOBZe4Xsxw8MEHF8dCYOwDtnqdNBGw1u37+vPx+tIYiADQf+9+97vLh6d8K8mc+CR6y6CIgYeUOmdUCJOoHgIHzAuGSfsasTJi6lSdxyNoFztxvT4qHCbuC746wXB8gIdUCFz1cz3veP1/NifvvZBVsbym2HyUjFd3EjPqfwecxm4dAh57YVRI8HkCC3bzyYa+kQEmHaTzfJiJ6ut7MmwVz4aSrD6ilvH8hqDANyQYh4IrcKRP2aX29hV9ZAXUdvgiSBwk65BS54waVQRDZEVIkAapXadIUZ1DYhp9rfQXCWQjLPcc4B2CRDVwYFYe88BOVQ+cXeNvaPWhofoApl9t6Sm6zAZmcQymP+EtA12uvQ/PaIFdq4zk6au9nTMqBEk+0UCttBDbdzD7ZAIdgegRPNtPxAq3vZF3aAmciI0qJ7oL7Bn9+xjohoYf8MCDvoQrmxQIuBcNZ2Pu4Go7uL3LuSSm2x5KQ0mdMypEBFlCt9gBvKtGrD6YFSyBySDC4eC/T0z2Ac8swsCY2Y7Fqo/A3veIPwvuLp9HAgqqf+5zn1v2YbYrB+99BMV29IYePJPgdiipc0aFRAkySCxzg6RYX4SWTsGU9sghTX0rh3ppRB5aAq8v4gnAsLCB5JDAH9wODeYu4YEHODIvag2xoBV793IMugdHyePcTGHODIDN533975xRw5BGNnYAosOosQX6QIQO0zG25Pz4xz9evsZlSVl2l0uHhqn7gDF1goVkYN/blT3SA2whsuTdFc7wUT/gwOClH33qU4CIzzCSlPV8rif1p/skMfUXboWRGrDzbl847ZxR02BIgjxxtILzrabvSyKAxeS2uVOT4LYCBedQE2IUL22KBlGB3zFkmNeNyzoOMJZYXkz28Db3+9cAACAASURBVIc/vDgGMd48A5k8hAiNBW4xfZ1m192O7crvnFEBEoKCEARn3jIRStsBuq77OgY8iUSyyp/HN52zrnpXKdcAxznCEQfupL4GutTf1xmT6kcM6uxL5OJ5bdnJjKGtuQ9vs5I8ynPOdUygPvHbG6MGGSJtSFOqintdJx1o5GTPcMeTpukQz4aWDCAIyP6zbC5fKgMnmBHkrprCrHYO4eW1yD/fBmLCwNk8KXQZYVI3ycKw85TTdp5eGBUyIAJx2Yhb8IPtThBc18gAB4lO7fVVL4uzwZcOaxvhq5YX3NklwxSXLUSHDO+q7Z31ftrubDrlhBNOKAPvkUceWRyVGXSDt3nK844j77jOYDjr/XU974VR641hC2AOHkwrViDEAUnO607qsfO5Ock73OEOxYFk9FV3PKrrhmGR8iMZSFMLGziUpC5wtQicXeWt08kZZ5xRIrZsq2LxQnC1CCwGbrhEl+xa8d5hWOe+Uu+MarSi/vrmqOmRrpNOMXdq6Z2FAukMcC3T0V3AH+I0wBlg4A68u2KCC/1ksOVAYpOaA08/LooTeMSsiQXmkPJfWrbMRWGYlL/33jVqcYywD7/whS8UgguyuiA+tjE7jxPJlIdOScdMQljf9xAL88DZjg/UPdE30pDhXhfe4ML2NL4kTsvwNTaDbgIbFq23rpnUGdN1n/jthVHT4BCc4AKjolBC6iak5FgU0fPk1xnKFxXla94cBhwPBgYd3HenTGsD2A1ucMhOBTOzAcx1IptWxqY/01Yp9ON7tQZcq2IM+nATGlu0regw5cNnneGXLXNRGCbl74VR64AgNNMhDitCgqh1ISUEzdPL/iBNfXgp0rQO2xCv4UUbnO0+ITBDNJV7Q7Sp28ahdqIZTOos/PTlL3952RzdYAsvoZ2cF4FB+RLp7P0sdVumrEXqnZW3d0bFmAKgOUaMihxKktFsXciBfFLJrvMWrpuS4TzYJIkUghUah1EFbCDcXSGFSXnreXmzebZINzRTPxbFB7w6rJVWDryuiw4Xga33niUFMA2pZj8b0TbSOpGjPnO3PjZ7zWtes6z2B4dBYxMSQgp+9t577yJdhGHuChI1A7izHe7tH3XccceVfoSX0A78BEfL9CmJKhnUU+4y5bT1Ti+MmoZjDFLAf946yI9jRAOTr63GKiedx3Glkw888MCy24SOWUd9bcKuLDhLGxLZhUHZ95sy0CyCk7RV36AP0tQh2F4EkuWI+lD/oaXgYJW+9C7TKLiuDw6LwN5m3l4Ytd6AINduDw7zghAT5NTztnGNqNXJNuVptrYTMej8TUxsayuQ7EoRIt3EdmwHM6apH/rONN6LX/zisjjBvrzaL49nbST0EIddIpMCQxvlL1NGOy1bpubGO6Js7KNkhz1MA1mYte2kXO58uziQ4uZO08GebVpi39sHaFM+urUofsMgORtcTz755KIN2eHeR8cMvp630X/KcLBRJdNfKbvuAV60Havm751RIzk5c0gHqm8cSm0gvokgZXIiWQRw5zvfuSy1k2cddTXrXsd/Kl/2+kXEOy2FQZ0le0GfddZZlZ0E7WlFiyD92tYmlClFoqLTwFAedPzTO6NikEhQnxYUZWNeMFJuVXxALmRL6hFp4nsy1nT63qn61dVWfavCO+v9EAu4c8Cbwe1jH/tYkS7uS8k7q8whP9eG9M+Xv/zlEn1E1T388MOLtzewy9dGe4M7dcZGDZ5TVx/nQTAqhBixeH65w+P5bcNuhGSjo/KVR7XmiLCvq88YbnrSPitpqGq2Zol6Fk1l09uHNjh29B0vr/4TfWTbVG1sO2F2OFW2wyDfxgCwKpy9Mypk6ATMJOhBB/DGutcGgoJwZ4ltyuV+yCGHbIwUndbJiMoKJAdNRDvbwNu0Ort8pi0GIaubeHkFNey3335lQGpb3dUu+IPTDHgZJDzrE6+9M2pUDCMXh5L4VRLVPGdbHQHxDmo1G8fcI7vOvZ2QEJf2ZMcHbYK7ndA+bdAuAfd2A7EYnF2+LkmnPvi0hhWztumoWoXWemfUAB+iEveLoRykalvJaEhSU52MyEbpNstvC85lykG4e+65Z9nxQdBItBEEt4kJ3NrgLMzz1a9+dZknFsu7xx57lCYZiNYh4ZSJFp3Vn+t11LVI3/TOqCEmo5dRzKjpQ722GAnzLtKgZl5lqIMTydel7XwoZBDiN8WB1GxT/X8IylQTos5OGQh9EweiMARJRmpagmid6X3uc5/iV8Cg9aOOizauQ3Nh0Gh8+d9GHcuU0TujRkXTQToHo0p2LgjSlmlY3glDmvYx1yiKxajcRtmpo8+zdhiI4M1gZ2ED4nIPbjcxaROfhegxX1+zr9a97nWv0mee1Y+225eBQv2j6lvDLsQgqhy+q0KNM9eJcVdNQbyR2QhNmiJgxKwjNj0hWu0RLIKgrSaJ2ginm5ZiE/JRsEup8r//+79f2qed+rN+tN2+0AtzgnnE8Qifud92ffOW17tEzegIYMwThxJbkgq8bEKkGNPZx4HOPffcErjNWRVJ0zfyl21b/T1t0EZn01scL+ZUERfcbkIKnFHVeVoNrGeffXb5XoxvAGEc9LHuZPCGSzBhVANH7nVR/3btW3/Lt6u5cR9iIILKIazPSGq/3zaSAAerS0ySC3RIR4RA2qij7zLgzuZs7FTMirA3tX3MlBNPPLEsfbz//e9fBlZ91kVSjyOD3xCkqXYPglHDpFFJhRJyLLFRVk2cSALwbay9zz77bElZdXbV+au2Ydr7wR2CEvfqfwa4TWyf2FrbfRpwfCKRSq9tfUmzmF/w2mcaBKNCAESE6MKo1N9VE+/xhRdeWKJ3bEtqMFDPJhLxJFwgYsREE/F5EEH6FsOTCH0T1yR4Z917+9vfXtReklRopH6K6tlFn9Xp0DU8JnVRf+pqnntnVI2vHxBjcyrTKIm0QYzzJu8j3BApO0ewOm+vZ2HUdMi85Q41n/Y4tM3CBjY4DYIE6pOw5sVXBhqwGmA4kDDoEUccsdVXKUs7153gMbRhxwghrZGq6657Wvm9M2oTOEiCIPsBWZtquw1Jh0LirOT9dKh3MartSpbd53VWfUN5rt2xU9moAkY2IYGZ8+g73/lO2VYFwx599NFlbXJf6u4Q8TY4Rg2SrGxhr9R3gs+zWWedjXCN0D74m6D1TZAws9rWfJ62hlGFR7LvRWFtQnsNwOC1k+DFF19cQgSj8mrTmP4PA4Nj1KgeCI5kFKSgM+ftNPkcpmZ8Dt50z81vfvMtW2endjzp4xDzy6YT+DAvzvrECZjFX9tJ0G4bgu7RQOigT9iGVPfgZvwRF8bMjg/5ZAOkzUN43iVJ2LemZe54xzuWb9sMCeltwtLECbNB5JUpDkwQiRv89S1lMaAB2EAqMU9OPfXUAqtPJJo+6zPBJxyZ3kKDdgPpG2fwMTiJWoD6/4EPplR4bdkwQeCsTmT4IwYOFVElBx98cFlg3CToWeVs6nPe36xAMmhhVm0fSvvBoX8kDGDp2gUXXFDZ+wjcY5qMgcExqs4z4ma64fOf/3xlZb8Onndk45iwflHgBFXQ6D3vu5PRtDl3qb2maXyTxnYzmELbh9J+cOhLA4gwUdLUIv7b3OY25d7mYLpbSAfHqDqRJJBsyl2PUPJsnsTmMQfr62xUwRBpzvOUsal54EgoIc2C6k8bcT2UtkcdN/g++9nPLjsI8vJSM4cC4xD7fnCMCklR16wIIV2zkiYqUxOROjjPSE/S1PQOh5T7pAwCVtZOT9qLUcWpwhtbS6rjqEscwLu664fB4w1veEOBz0Jw34sB97wD8TrhB6cUejGPGr9Hnq2z/u3KHhyjQkY6TCQR1fUDH/hAUV8x8KTkfp4ZqX2CzxenbU8Spp/03k68ZzBy+JSllTRCKDFBHUddtjv96QwOZ/35yle+smyHc/vb375I/aH0E9oDCxwa4IeSJlN+j9DpSAmyRCjZQwnzUYEnJfljgyIEIWgm+y1nY+dC+FCIYBL8bd8z+iMwZsNXvvKVrS1t3IefrpP+ycBLBdc3VF7eXR8cpvKaR5Un+bqGcVJ9YdZJz/q4NzhG1VlhVgihFlnuhlknJXlzcKC8853vLKtIRCIhzqERwKQ2rOMeiWpNJ2Zt4nQd9c1Tpv54yUteUnahYJeK6TZ4DKmPIvVDU/O0q4s8g2PUSD9nBw8mO2HaShoSxGh9ySWXlHkvG2vrfPeD8Jy7QGrfdWAIeIMDdirc0Cz6SGAAD/yLPHrTm95U5rbtAule4JJvCCnwYlj0A3aaGVoEb19pcIzaRISvrXGIILhJCULNlyJGi8OpUpxIkOvZrppIK7h4z3veUxgWHvpgBv3iEMr53Oc+t8TwPvjBDy5z24h/aCkDugHERt+EBOeX+33COzxMNXrOXr+YlWNkEuMhPkgV12vinG0qMgdxTMrfKH7H/YUPgxS7z4Bl9/wEjPTRWAROKnEe+eLcQx/60MpOk30T/na4wIzoCXzO6CgaQR8DXeAcPKMiOI4Rqq9wrmaCWIj0MV9INXcKyVFXmvl3+n+4MEAhKgEfvnzGvocbeOk66R+ajqD7Qw89tAQ3gCVM0DU8s+qDP7jLMSt/V88Hz6g61RYjvIWCGPyPpER4EGu9KWlq1YUNvjJ32OcI2FUHNuvRZoMU+4pDiTSFN/+7UN3SJ876SWSZTyTasM6+vNbMGnwlMA0twR+acmhDJKz7obs+YB48oyK62Kn2PYI4CIQ4Z51tXi4fJb7Sla5U7nu2KyaSKhKVislOZd+71wVO6n3DvrOtioUVD3zgA7c2zx5yv6CrMKeoNkIgwqGLgW473AyeURGYLUQdWfKGGEJ4iOHMM88srv4DDjhgixgxMKTviimDmI9gYVQribpgUrhO34CByutbP7ZVEcvbFQyr9nmEAcnPUZl2rVruKu8PnlFJVN43UtWmXYIbEEEibqhWgrutOc3nDjwPI6+CnE18FzNovwPBmYembcCHY91JneoxODznOc+prnvd61b3ve99C5P2KZEWbXcTV30PMoNnVLYCqWBeEKNyjkBi7Jt3vetdZR9bH7UNkea8aOfshPxhBmfHXnvtVXbK4BWX4CZEh5lXTfoi5SnLf1KIl9cOHccdd9zWeuB6vlXrXdf7GeQz0KknuOwT/sEzajrf1iy8vggOEtlimPatb31r2RPphje8YScSY10Esq5y7RdlsPPt1HUlhKyOMKk+sc7UV8FNEbHxQuzrgqGtctGWQyIMaHDa1ncaPKMaxRAAxwiP4Uc+8pEygrtnbtWaSzsM1pez9Y3UIdXPHGCrcuisg+DCpMp2WOifbVUe8IAHFA80L7yBtU+JNG+foKswKhuVibUOvM0LT/INnlERAsTZiJmdGseIaQefPUCENi+DzEzLpHHjuSrL3UzTxE5tGyeYT//AvU9pPOMZzyjbq2BSA6vnOTDB0FN9MNEmEhXcaUNf8A+eUSEIojiVOCaEogk2NzeIUffff//iREIsm0AIXXe0gU44oYARO1/UpcMy+AohO1NppVy/4x3vKI69Bz3oQeUbtJ5loNU/pOqmJPA6tM05bekL/sEzqo7WwUZnn2xgl1oRgkmlgw46aGuCf5MIoasOx5gkKmnHQ76uxAzJV8Hvdre7lUFzE/sjzGkQi4CAQ3TYZ+q39jlanpEN0qi+RnEf6z3//PMrH+8VJmfUg0znMV0aA5iF5xf+BOi3nfSHoIBTTjml1PGHf/iHZa0pDUidm5w4k9AUO1Xqk74Gz6g6OwiyiJyBz/UvSok0teWIPFGxNpkw1gE7G8sCfNvamG9uO8H9q171quqiiy4qIYJCOCUD5yZK1OAH7GgN/jJnn2d9nAfHqJiyfgQpEGclDWY1n2qbFlMPUVViRyS/Mpr38mxXOsMbp4itONmpVGBpWfwE3xgRk/LCv/a1ry0OvTvd6U6lLpLIsYn4D8wYFO4iVdPuvmhncIwKIfWDpIxUZadSd02oY1IeX95fqemdU0bU4UmM3xfCu643jGphA/ueM25ZJgW7dyXlcuo973nPK2s27djgS3KbnkIr2pdrtNS3xtY7o2LC+hHk5IzZYsi7RzL4b0LdTg4cGCbzfU9TOZIzxpUv5eS86YS0DPzwYPUKe5JUDV6WKQtu4VK/2EnQRnLWmFqKiKB3Qgqt7LbbbqU54sm1u8/29b7OSIfXUxMZkAZJOdil1F7zgsIHn//85xdHBrWYfcRxIpyQ40ny/q6cMCUcY1Q2l3lo+Ml9kmORpB9oNMo59dRTi2Zz17vetRBxpNAi5Q0tr/bBjbOVWK6FQqIjtNkXPfXOqHYXPO+888oHnWycbXtQn7IgEc37sRHsr2NBuBHO/5ve9KblsL5RZJL3HPZMsi8PD6SpHPvb7rfffmWdKrUsnsgQZ51Y0xE6I4OH55uYQkxpJ6ITL41Z4ScEl+fT2ggX8surT5TNyyuwQX884hGPKA49ZcgXnAWGaWUP+VnakXZrGzzSStCR9uXwTPKOPA7XKaONdvbOqCShmFCJY+LII4+s7PWKIRGEnQGe8pSnVJ/5zGeqxz72sT/gSbTRNsY2d4eQfBvUxDuVTMwpRwdJIlZYqOGNbnSjwsQcLEFwzjpBvTstIRghluKhLQk0OJIWCGpWe0OozggT4/Ly0miOP/74sjqHaoh44U++TU+hB+0Nw7nnfwZ7/+sMmcE9bfeee23ho3eq1FiNTke7TuOM2Le73e2qs846q3yQGENbtlVPQZaz90hkUxGIhrODlDV/6PMOT37yk0tdvmYuWJwaLb+1rpKO8F46x3/wbHrSDocdMNj29lESdjlvgtfgpb55Nh+BwVHfSfC26ane36b+pDgstQ+dwUWdCf2HA/nkCR21iYveGTVMQeqFaUNYkMbTi2Ehw8jdTEGevN6DQNcQJz6YPWZBufdJW46nCy+8sEjd17zmNWWOkaQROHHrW9+6MLkyU16zvk37DyfaAy885tplDnqfffaZKzY6OMWsIpue/vSnF2+7zbMRsvKUDb8ZYDcNR3V44UqbtSuxymzUJFFx55xzzhatpc0GLNodp5rZCO9LszSWlDvr3DujapAjElHDw3yAp2L51qc4X3OoQUAaFkL0P0jLM2Uqy4Fxqb0Qeb/73a84CAQAkLbOr3jFK4pjim3rcximM0hdn8VQB4QjRtcJ1lZuYM916h7KGXzBkcAH7eEIAq/2RBpuB28GT4MkM8JOgk972tOKvZu+aIsYt4NhkfuBKe+EBgwm2pyBPM+DG//lJRUJDd5xppjBiKmQdzkybdJmoBLkcY973KPQJR8IOjKQ8Qf4po55ZfVJq+Kod0YNwnL2gSdrTjEdovDlbKrs4x73uK0RTt5mh+T9JrPqiHrynoONxmZ16ATSwjdVbR/CuXX66acXAjcd5BurbFwDBVtPZ6YcHZHODlE366v/7+MafOBFTJYLUn212b1ZSR7t5YTiL4AvWgomN2A18TurvLafN9vQhCcMJl+kvjzpK5KQF9tXFiwFZCrZ0ZJPRNLf8CYf2vKee0wm5pRB3+AefGDgxz/+8ZWPMpO+HJ7wtGoaHKNSQX0vE2IwKjvT5lxsq4c85CGFwSB9O0JrdlwTQRDtiIRUDkK8+tWvXh1xxBHFsWXHQ1JcPLHdDU3qO6jSJLv9f3iUObGUpSNCBLPqb8Kz7v91wgUn+DHd17/+9bIZtvbPSvI+85nPLEz+6Ec/umTXTm3vu7319gGs+T/9op2uDay0A9FtBmS0hUFtqZq28IMcc8wxZaoPXVjTi17SXmWQuqFB/z1XNwHA+UldtuG46UKzFKumwTHqVa961SK5NJo0Y0sJ9H7Zy15WVAq7rE8jrmZHBflBlFFRHsgNooNkedzDkOwMqu8jH/nIshjaKGsKiDOFjaJDbA8DPh3hHGmbupzbGE3r5S16jbi0KW1GOHBJTaMpzEriXH0vhipoSoYjTlnw2sTtrLLW8Vw/1tMk2iAtre7BlNRZ0jJ7HTMFCIfDDz+8mEVozh5dYfDQk7Oy4UOfksLqdh/Thp7gm+prOpFZRQvhxJNnlTQIRk2DSdEkRAAJDHre3rPPPrtMuXiO2TwPMvPOpHMQXX/m3bqKPIngcg8TUxdJT/YIGKnjOoFj6o1vfGMhfLYM23bfffctHWPOsj4Kg0OZOlJK+f5PgiXPJ8Ffb8usa2WrI/VyKEkIFjE1k3yBFX6ZA6Z0DjvssC0zofnOuv6DBR6Ct+Y1+IKn5CEtaUNRY/k4rLaSOCUzuHIg8nxTW+tJn0nb2e5huOBTvfCFiV2jA/8xPLpGJ5MGj3qd81z3zqjpDMBqaIg7jdPob3zjG4Up69MoyT9PI1fJo/4cqZNUYrNiWkEZpBM1yqhNXZZIZN5mC9vZM+aLpbQvI3D+e6aedHjJ3OIP3CrbaA8e0oVUCOHVqwITc8AeVZwj1D9bfm5HvPV3V70OXpQTmOGlntxHNw6hoySkrWTZjAZRzIqJOc/AftRRRxUVFHOSlsF5BrF62ateg0kb9L96mG5wuSruemdUiEHwPq2oAzQyjfXfVIIwQYRuTtW9dJzrdad6Heo1YoLRfR3h/21ve9sinQRoGMmpxyQRu9oUkAGGQwxzi7JCPDpOByqHKqXNGClta6tdyksbnBEnRjXSW0nTZFQE7tBGqq5Afva5qQf9VJf+bcFYL0f56gd3GCr4hiOEzwyhzRgY2ZpoBy6p5bQaAyk7kxYE94HZ+66V5wwfEQh1GFa5Brd6DBbKh9/Uv0q5vTMqQkDUook08OSTT654fhGyZyQWNeLe97536YA6MbeN5EmITB06wBGiyf90AtipVqZ/TAOJsGIHiZDiSTTan3DCCeWwNYrvt9qL2DQQl79y1RWmAkv9ehJsi9xLO5RpxwcffGa7RUtJWSFkpoZYanG81HmE15W9jUHhgz1o7puabgDEmJ/97GfLgMFHQG3lgWZjGnzEd/MT6Avt1EdS8OjsGVw4wrBpu3Peqd9b5Dp9SMAYcNpwJKm/d0alnggZdEhBapDT/B+Cy/N1n+sdB5bAk7P66zAlv+ccFaQnL7E8Os/0j/k3g5NvhcrHacWxQzXjlWWXh6A8V6YjdbpWnjwZKLbDQ96pPydtSCDqIkmfOkLgpqpoMWDxKQp1YFKEN08KrDmHIfx31JO61eswsIndNn1kgOO8M4epbnSCMe95z3sWfBng3GuWpxwp9zF9UrOf/E++5Jl1lj/4yrX21aW/a+GrzAy2/aw+mlWn599vxTy515CnOUoH0alqEqHl2RDPzU7RmbQDRG4eFvGbZjIFZL6Y1DIFJLyRNNC5iJB9i4HZOghKuQiC+glny9o94EHwYCLpTcoHx87KpdVgGN5hg42kX5ptm4T/qK2ehXiVC27tcC2PttCWSEs2Ptsyaqx6TIloP1XWVBitw3ym97VBHjDVmW8SPG3fAzf44Q8crtM+/x2W//mUh/hzPgr3Vk29M2qzEV0jflUENt/Xac2EoNKx2uv/7rvvXqZ0eB6pePbD5Z3klMK4JC/Gpc6Z+mHfYmA2cYi+ibtmvZP+e8dgYMrAfCpCCwPJf8YZZ1RvfvObyw73bD2EWX8+qcz6PcypTCllu1YOjUL4JkeW6CjeWWV7xwBmioS0p1kYoLRVArM82u0cGnE/1yVjBz8GCPUyy1zTAtjv+pdqftpppxX730J6uzHKM4kmFgX1Mt9T6zZpyqNt3mj/dhOGNhrdPpTbl4hYm6O/NoSItQ/jpp2kJYcJ9Q9Rc0xhYPk5S9i/bFuMhokRyCIJsavfZDxH11ve8pYy/aQMjETVRXgnnnhiYWj3OUTSjln4x5DqSKCK6REETHvgRfa+eWp2MrWbTc9eZyurQ4IPDClvGNG91O2c/7lXXpzwM+v5hFem3jIDwbNvkOOMC3zqoYqblmOXapv2aIf+T76phU95OHhGnQL7LvMIgXO2sWsRvNA0DGpO0Aog6iF1lpSWEAYiCXGEYDxDUJiJ5BZ9Q82lnlFDrS3FWAIcOGjkrZcV5lCuMvJcFI7oJbYtAjbAsH/lJ715X8GaQQYxK8PgFBh3emfC1SppZNRVsNfBuxhCQtQ627whyYdpHZnMZ79RH0lbq4AS9uY9zCZhHCO8M+8pj675UTYzyWq978Me9rDKLvdS8irD4b9z9ghmW5oqAQ+nD4Ylfdni9rRiY2JK0pIaH2LVJmXlf6lsh/+s2taRUQdOIBgDYZM8JCMmwwzUSwxIunIKJeiCzeQ5bzNJya5lB2MUZXhfMvfI2cEeFBDg04iY6qSTTipSEGFF2nF8Kd/cJdsSY7LRwEWNpeqRwKbRDBaZuwxDqlN52qLMtAUcGUQG3g0rgzcy6sooHH4BCB1xI3SHhMDDdBjYfwEX5h3N2f7Zn/1ZkZpsRYyLmSx2wLjUUOUde+yxRSJjVvOUAhvsO8XJgxnZlryxnoliolqzX9lf3mFbkp7mj8OEznV467AiVs/SjjDt8HtgdQhHRl0dhxtdQohfIxB+nEUYgt2J0Tg/SF1bhZJy7Ea7Mwi098yUDEYWiJGVNVRpzI9xScksPhBooB4pTOe/vGDJQLLRSF0D8COjrgGpm1Rkk1FJ16jKnsWR5OzDWpxFvtvDmWT6g6SULwzMxjUVZJqEtOS0yly3fDngKEzpHmZ1zr1NwmEXsMLNKmm0UVfB3gDeRQAkm4RZwqRRLz13kJqkXvJQidmd5jSps1bVsFGTJ2WmnLrEDDOmbHW7lvKs/Bl/tjAQ/GzdWPBiZNQFETa07AggTIUJY6+657+zPBg4zOZaPkyVe67li6dXO0NcnqWsnD13nTzBy8iowcSlz008Xfrp7H8jo87G0Y7K0WSk/MfQmDYpKnP9vryrElzK39XOq+JtZNRdjGKaBCN8kR2KISN9kyf/M39Kgo5pOQwEp8u9PYCg/GUBH99rDwOkp2AFQRDmYYUqmsLh4RVx5D8mjZRtr+axpHkxj1FTWgAAAlVJREFUMErUeTG1Q/JF1U1zTOHY+Z4nmEPJDghGf7HGVs6QtnbVk7xLuo5pcQyMEnVxnO3Sb8TmNN8qOknIoEAJQfrihTEj6Sn43Dd87ASJyFYltF0a6S00fjQ6WkDiJhWB4aiwGNYKGdMz9kwWcugej7CzlSB2fBQEYXeHpiTepDbvBFhHRt0JvbhgGzCj1S0C8cUBi9MV+MDrm+kaRdq6VeC+EMRRqi6I5Jazj4zaMkKHXhyGY3dadSMIQiA9VVe8LgaWcpZX+KAzKTtK1f56d/QM9If7XmrGcJJ1rUIIRSVhREzojGnz373RedRLN/1ApaNE/QGU7OwbGJHEJE05lDBjJGWkZu5NOu9s7Ay3dSOjDrdv1gaZIHtrRjFq9p/FlJh4EnPW760NqLHgqRgYGXUqenbeQ9KU48jGZRjTWlNeYMzYlKhaX2dS12PqBwMjo/aD995q5dXFcNmw2iJz26hg4NimAc5/a1bzfVD/x9QPBkZG7QfvvdWKSTGr7Tgf85jHlMXlPl2RudJ4fElXUzjWsIpW8h4JPKZ+MDCGEPaD995qxYBUXYmEtGWLzb/Nmdr1wZpUtqvNsNmy7mHQSNtRqi7XdavibWTU5fC+sW+RjDkQDwnqsGO9PZIwqe1XbO3pw1wYO4EQG9voAQA+MuoAOmEEYcTALAysyqij0TELw+PzEQMDwMDIqAPohBGEEQOzMDAy6iwMjc9HDAwAAyOjDqATRhBGDMzCwMioszA0Ph8xMAAMTF09s6qnagDtG0EYMbAjMDBK1B3RjWMjdjoG/h+/UuHGjP4SPgAAAABJRU5ErkJggg=="> <em><strong>A2</strong></em></p>
<p><em><strong>[2 Marks]</strong></em></p>
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>two vertices are of odd degree <em><strong>A1</strong></em></p>
<p>to have an Eulerian circuit it must have all vertices of even degree <em><strong>R1</strong></em></p>
<p>hence no Eulerian circuit, but an Eulerian trail <strong>AG</strong></p>
<p><em><strong>[2 Marks]</strong></em></p>
<div class="question_part_label">b.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>it allows Pauline to go through every door once (provided she starts in<br>room B or room E) <em><strong>A1</strong></em></p>
<p>and she cannot return to the room in which she started <em><strong>A1</strong></em></p>
<p><em><strong>[2 Marks]</strong></em></p>
<div class="question_part_label">b.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>for example: A → F → E → D → C → B → A <em><strong>A2</strong></em></p>
<p><strong>Note:</strong> Award <em><strong>A1</strong> </em>if the cycle does not return to the start vertex.</p>
<p><em><strong>[2 Marks]</strong></em></p>
<div class="question_part_label">c.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>she can visit every room once without repeating and return to the start <em><strong>A1</strong></em></p>
<p><em><strong>[1 Mark]</strong></em></p>
<div class="question_part_label">c.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>Z → V → Y → X → U → W → Z <em><strong>A1</strong></em></p>
<p>6 + 4 + 9 + 7 + 10 + 10 = 46 <em><strong>A1</strong></em></p>
<p><em><strong>[2 marks]</strong></em></p>
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
<p>attempt to find the minimal spanning tree <em><strong>(M1)</strong></em><br>VY<br>VW<br>UX<br>XY <em><strong>A2</strong></em></p>
<p><strong>Note:</strong> Award <em><strong>A1</strong> </em>if one error made.</p>
<p><strong>Note:</strong> Accept correct drawing of minimal spanning tree.</p>
<p>weight of minimal spanning tree = 4 + 5 + 7 + 9 = 25 <em><strong>(A1)</strong></em></p>
<p>since Z is removed, we add on VZ and ZY <em><strong> (M1)</strong></em></p>
<p>hence lower bound for route is 25 + 13 = 38 <em><strong>A1</strong></em></p>
<p><em><strong>[6 marks]</strong></em></p>
<div class="question_part_label">e.</div>
</div>
<h2 style="margin-top: 1em">Examiners report</h2>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">a.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">b.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">c.i.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">c.ii.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">d.</div>
</div>
<div class="question" style="padding-left: 20px;">
[N/A]
<div class="question_part_label">e.</div>
</div>
<br><hr><br>