Date | May 2016 | Marks available | 3 | Reference code | 16M.3dm.hl.TZ0.5 |
Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
Command term | Show that | Question number | 5 | Adapted from | N/A |
Question
The simple, connected graph \(G\) has e edges and \(v\) vertices, where \(v \geqslant 3\).
Given that both \(G\) and \(G'\) are planar and connected,
Show that the number of edges in \(G'\), the complement of \(G\), is \(\frac{1}{2}{v^2} - \frac{1}{2}v - e\).
show that the sum of the number of faces in \(G\) and the number of faces in \(G'\) is independent of \(e\);
show that \({v^2} - 13v + 24 \leqslant 0\) and hence determine the maximum possible value of \(v\).
Markscheme
the total number of edges in \(G\) and \(G'\) is \(\frac{{v(v - 1)}}{2}\) (A1)
the number of edges in \(G' = \frac{{v(v - 1)}}{2} - e\) A1
\( = \frac{1}{2}{v^2} - \frac{1}{2}v - e\) AG
[2 marks]
using Euler’s formula, number of faces in \(G = e + 2 - v\) A1
number of faces in \(G' = \frac{{{v^2}}}{2} - \frac{v}{2} - e + 2 - v\) A1
sum of these numbers \( = \frac{{{v^2}}}{2} - \frac{{5v}}{2} + 4\) A1
this is independent of \(e\) AG
[3 marks]
for \(G\) to be planar, we require (M1)
\(e \leqslant 3v - 6\) A1
for \(e \leqslant 3v - 6\) to be planar, we require
\(\frac{{{v^2}}}{2} - \frac{v}{2} - e \leqslant 3v - 6\) A1
for these two inequalities to be satisfied simultaneously, adding or substituting we require
\(\frac{{{v^2}}}{2} - \frac{v}{2} \leqslant 6v - 12\) (M1)A1
leading to \({v^2} - 13v + 24 \leqslant 0\) AG
the roots of the equation are 10.8 (and 2.23) (A1)
the largest value of \(v\) is therefore 10 A1
[7 marks]
Examiners report
Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.
(a) If they considered the complete graph they were fine.
Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.
(b) Some confusion here if they were not clear about which graph they were applying Euler’s formula to. If they were methodical with good notation they obtained the answer.
Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.
(c) Again the same confusion about applying the inequality to both graphs. Most candidates realised which inequality was applicable. Many candidates had the good exam technique to pick up the last two marks even if they did not obtain the quadratic inequality.
Syllabus sections
- 16M.3dm.hl.TZ0.5c: show that \({v^2} - 13v + 24 \leqslant 0\) and hence determine the maximum possible value of...
- 16M.3dm.hl.TZ0.5a: Show that the number of edges in \(G'\), the complement of \(G\), is...
- 16M.3dm.hl.TZ0.4c: Find a simplified expression for \({u_n} + {v_n}\) given that, (i) \(n\) is even. (ii)...
- 16M.3dm.hl.TZ0.4b: Use strong induction to prove that the solution to the recurrence relation...
- 16M.3dm.hl.TZ0.4a: Solve the recurrence relation \({v_n} + 4{v_{n - 1}} + 4{v_{n - 2}} = 0\) where...
- 16M.3dm.hl.TZ0.3c: Show that there are no possible values of \(n\) satisfying...
- 16M.3dm.hl.TZ0.3b: Determine the set of values of \(n\) satisfying \({(13)_n} \times {(21)_n} = {(273)_n}\).
- 16M.3dm.hl.TZ0.3a: (i) Given that \({(43)_n} \times {(56)_n} = {(3112)_n}\), show that...
- 16M.3dm.hl.TZ0.2b: By first removing A , use the deleted vertex algorithm to find a lower bound for the...
- 16M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.
- 17N.3dm.hl.TZ0.5c.ii: Hence state the value of \(a\).
- 17N.3dm.hl.TZ0.5c.i: Using your answers to part (a) and (b), prove that there is only one possible value for \(b\)...
- 17N.3dm.hl.TZ0.5b: Write the decimal number 1071 as a product of its prime factors.
- 17N.3dm.hl.TZ0.5a: Convert the decimal number 1071 to base 12.
- 17N.3dm.hl.TZ0.4b: Hence or otherwise, find the general solution to the above system of linear congruences.
- 17N.3dm.hl.TZ0.4a: With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees...
- 17N.3dm.hl.TZ0.3c: If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the...
- 17N.3dm.hl.TZ0.3b: A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning...
- 17N.3dm.hl.TZ0.3a.ii: Prove that \({\kappa _{3,3}}\) is not planar.
- 17N.3dm.hl.TZ0.3a.i: Draw the complete bipartite graph \({\kappa _{3,3}}\).
- 17N.3dm.hl.TZ0.2b: For every prime number \(p > 3\), show that \(p|{u_{p - 1}}\).
- 17N.3dm.hl.TZ0.2a: Find an expression for \({u_n}\) in terms of \(n\).
- 17N.3dm.hl.TZ0.1c: By first removing library C, use the deleted vertex algorithm, to find a lower bound for...
- 17N.3dm.hl.TZ0.1b: Starting at library D use the nearest-neighbour algorithm, to find an upper bound for...
- 17N.3dm.hl.TZ0.1a: Draw the weighted graph \(H\).
- 17M.3dm.hl.TZ0.4b: Solve the recurrence relation \({u_{n + 2}} - 2{u_{n + 1}} + 5{u_n} = 0\) given that...
- 17M.3dm.hl.TZ0.4a: Verify that the recurrence relation is satisfied by \[{u_n} = A{\alpha ^n} + B{\beta...
- 17M.3dm.hl.TZ0.3c: Find an example of a graph \(H\), with five vertices, such that \(H\) and its complement...
- 17M.3dm.hl.TZ0.3b: The graph \(G\) has six vertices and an Eulerian circuit. Determine whether or not its...
- 17M.3dm.hl.TZ0.3a.ii: In the context of graph theory, explain briefly what is meant by an Eulerian circuit.
- 17M.3dm.hl.TZ0.3a.i: In the context of graph theory, explain briefly what is meant by a circuit;
- 17M.3dm.hl.TZ0.2b: By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s...
- 17M.3dm.hl.TZ0.2a: Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling...
- 17M.3dm.hl.TZ0.1c: By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest...
- 17M.3dm.hl.TZ0.1b.ii: Hence find the general solution of the Diophantine equation \[264x - 1365y = 6.\]
- 17M.3dm.hl.TZ0.1b.i: Hence, or otherwise, find the general solution of the Diophantine...
- 17M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.
- 15N.3dm.hl.TZ0.5b: Hence determine whether the base \(3\) number \(22010112200201\) is divisible by \(8\).
- 15N.3dm.hl.TZ0.5a: Given a sequence of non negative integers \(\{ {a_r}\} \) show that (i) ...
- 15N.3dm.hl.TZ0.4f: Hence prove that \({K_{3,{\text{ }}3}}\) is not planar.
- 15N.3dm.hl.TZ0.4e: Hence prove that for \(H\) (i) \(e \ge 2f\); (ii) \(e \le 2v - 4\).
- 15N.3dm.hl.TZ0.4d: \(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\)...
- 15N.3dm.hl.TZ0.4c: In a planar graph the degree of a face is defined as the number of edges adjacent to that...
- 15N.3dm.hl.TZ0.4b: State which two vertices should be joined to make \(G\) equivalent to \({K_{3,{\text{ }}3}}\).
- 15N.3dm.hl.TZ0.4a: Show that \(G\) is bipartite.
- 15N.3dm.hl.TZ0.3b: Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).
- 15N.3dm.hl.TZ0.3a: Show that there are exactly two solutions to the equation \(1982 = 36a + 74b\), with...
- 15N.3dm.hl.TZ0.2c: A second recurrence relation, where \({v_1} = {u_1}\) and \({v_2} = {u_2}\), is given by...
- 15N.3dm.hl.TZ0.2b: Find an expression for \({u_n}\) in terms of \(n\).
- 15N.3dm.hl.TZ0.2a: Use the recurrence relation to find \({u_2}\).
- 15N.3dm.hl.TZ0.1b: Visitors to Switzerland can visit some principal locations for tourism by using a network of...
- 15N.3dm.hl.TZ0.1a: The distances by road, in kilometres, between towns in Switzerland are shown in the following...
- 12M.3dm.hl.TZ0.1b: Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .
- 12M.3dm.hl.TZ0.3b: What information about G is contained in the diagonal elements of M\(^2\) ?
- 12M.3dm.hl.TZ0.3d: List the trails of length 4 starting at A and ending at C.
- 12M.3dm.hl.TZ0.4b: A simple graph G has v vertices and e edges. The complement \(G'\) of G has...
- 12M.3dm.hl.TZ0.5b: Find \({2^{2003}}(\bmod 11)\) and \({2^{2003}}(\bmod 13)\).
- 12M.3dm.hl.TZ0.5c: Use the Chinese remainder theorem, or otherwise, to evaluate \({2^{2003}}(\bmod...
- 12M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where...
- 12M.3dm.hl.TZ0.1c: Find the general solution of \(123z \equiv 5(\bmod 2347)\) .
- 12M.3dm.hl.TZ0.1d: State the solution set of \(123y \equiv 1(\bmod 2346)\) .
- 12M.3dm.hl.TZ0.3a: Draw the graph G .
- 12M.3dm.hl.TZ0.4a: Draw the complement of the following graph as a planar graph.
- 12M.3dm.hl.TZ0.5a: Use the result \(2003 = 6 \times 333 + 5\) and Fermat’s little theorem to show that...
- 12N.3dm.hl.TZ0.3b: Hence find integers A and B such that 861A + 957B = h .
- 12N.3dm.hl.TZ0.1a: Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T ....
- 12N.3dm.hl.TZ0.1b: (i) Does this graph have an Eulerian circuit? Justify your answer. (ii) Does this...
- 12N.3dm.hl.TZ0.1c: The graph above is now to be considered with the edges representing roads in a town and with...
- 12N.3dm.hl.TZ0.3a: Using the Euclidean algorithm, find h .
- 12N.3dm.hl.TZ0.3c: Using part (b), solve \(287w \equiv 2(\bmod 319\)) , where...
- 12N.3dm.hl.TZ0.3d: Find the general solution to the diophantine equation \(861x + 957y = 6\) .
- 12N.3dm.hl.TZ0.4a: State Fermat’s little theorem.
- 08M.3dm.hl.TZ1.1: Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315. Hence...
- 08M.3dm.hl.TZ1.2a: Define what is meant by the statement...
- 08M.3dm.hl.TZ1.2b: Hence prove that if \(x \equiv y(\bmod n)\) then \({x^2} \equiv {y^2}(\bmod n)\) .
- 08M.3dm.hl.TZ1.2c: Determine whether or not \({x^2} \equiv {y^2}(\bmod n)\) implies that \(x \equiv y(\bmod n)\) .
- 08M.3dm.hl.TZ1.3a: Show that when p = 2 , N is even if and only if its least significant digit, \({a_0}\) , is 0.
- 08M.3dm.hl.TZ1.3b: Show that when p = 3 , N is even if and only if the sum of its digits is even.
- 08M.3dm.hl.TZ1.4a: Draw G in a planar form.
- 08M.3dm.hl.TZ1.4b: Giving a reason, determine the maximum number of edges that could be added to G while keeping...
- 08M.3dm.hl.TZ1.4c: List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two...
- 08M.3dm.hl.TZ1.5a: The weighted graph H is shown below. Use Kruskal’s Algorithm, indicating the order in...
- 08M.3dm.hl.TZ1.5b: (i) A tree has v vertices. State the number of edges in the tree, justifying your...
- 08M.3dm.hl.TZ2.1: (a) Use the Euclidean algorithm to find the gcd of 324 and 129. (b) Hence show that...
- 08M.3dm.hl.TZ2.2a: The table below shows the distances between towns A, B, C, D and E. (i) Draw the...
- 08M.3dm.hl.TZ2.2b: Show that a graph cannot have exactly one vertex of odd degree.
- 08M.3dm.hl.TZ2.3a: (i) Given that \(a \equiv d(\bmod n)\) and \(b \equiv c(\bmod n)\) prove...
- 08M.3dm.hl.TZ2.3b: Show that \({x^{97}} - x + 1 \equiv 0(\bmod 97)\) has no solution.
- 08M.3dm.hl.TZ2.4b: Prove that a graph containing a triangle cannot be bipartite.
- 08M.3dm.hl.TZ2.4c: Prove that the number of edges in a bipartite graph with n vertices is less than or equal to...
- 08M.3dm.hl.TZ2.5: (a) (i) Show that Euler’s relation \(f - e + v = 2\) is valid for a spanning tree of...
- 08N.3dm.hl.TZ0.1a: Convert the decimal number 51966 to base 16.
- 08N.3dm.hl.TZ0.1b: (i) Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and...
- 08N.3dm.hl.TZ0.1c: In each of the following cases find the solutions, if any, of the given linear...
- 08N.3dm.hl.TZ0.2a: Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph...
- 08N.3dm.hl.TZ0.2b: Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted...
- 08N.3dm.hl.TZ0.3a: Write 57128 as a product of primes.
- 08N.3dm.hl.TZ0.3c: Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).
- 08N.3dm.hl.TZ0.4: (a) A connected planar graph G has e edges and v vertices. (i) Prove that...
- 11M.3dm.hl.TZ0.1b: (i) Find the general solution to the diophantine equation \(56x + 315y = 21\). (ii) ...
- 11M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.
- 11M.3dm.hl.TZ0.2a: By first finding a minimum spanning tree on the subgraph of H formed by deleting vertex A and...
- 11M.3dm.hl.TZ0.2b: Find the total weight of the cycle ADCBEA.
- 11M.3dm.hl.TZ0.2c: What do you conclude from your results?
- 11M.3dm.hl.TZ0.3a: Given that a , \(b \in \mathbb{N}\) and \(c \in {\mathbb{Z}^ + }\), show that if...
- 11M.3dm.hl.TZ0.3b: Using mathematical induction, show that \({9^n} \equiv 1(\bmod 4)\) , for \(n \in \mathbb{N}\) .
- 11M.3dm.hl.TZ0.3c: The positive integer M is expressed in base 9. Show that M is divisible by 4 if the sum of...
- 11M.3dm.hl.TZ0.4a: (i) Determine if any Hamiltonian cycles exist in G . If so, write one down. Otherwise,...
- 11M.3dm.hl.TZ0.5a: Explaining your method fully, determine whether or not 1189 is a prime number.
- 11M.3dm.hl.TZ0.5b: (i) State the fundamental theorem of arithmetic. (ii) The positive integers M and N...
- 09M.3dm.hl.TZ0.2: (a) Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) . (b) Hence give the...
- 09M.3dm.hl.TZ0.4: Two mathematicians are planning their wedding celebration and are trying to arrange the...
- 09M.3dm.hl.TZ0.1: Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The...
- 09M.3dm.hl.TZ0.5: (a) Using Fermat’s little theorem, show that, in base 10, the last digit of n is always...
- 09N.3dm.hl.TZ0.2a + c: (a) (i) What feature of the graph enables you to deduce that G contains an Eulerian...
- 09N.3dm.hl.TZ0.5: Show that a graph is bipartite if and only if it contains only cycles of even length.
- 09N.3dm.hl.TZ0.1: An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence...
- 09N.3dm.hl.TZ0.3a: The planar graph G and its complement \(G'\) are both simple and connected. Given that G has...
- 09N.3dm.hl.TZ0.4a: Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits...
- 09N.3dm.hl.TZ0.4b: The representation of the positive integer N in base p is denoted by \({(N)_p}\) . If...
- SPNone.3dm.hl.TZ0.1a: Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.
- SPNone.3dm.hl.TZ0.1b: Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .
- SPNone.3dm.hl.TZ0.2b: Giving a reason, state whether or not G is (i) simple; (ii) connected; (iii) ...
- SPNone.3dm.hl.TZ0.2e: Find the maximum number of edges that can be added to the graph G (not including any loops or...
- SPNone.3dm.hl.TZ0.3a: One version of Fermat’s little theorem states that, under certain conditions,...
- SPNone.3dm.hl.TZ0.3b: Find all the integers between 100 and 200 satisfying the simultaneous congruences...
- SPNone.3dm.hl.TZ0.5a: The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation...
- SPNone.3dm.hl.TZ0.2a: Draw the graph G as a planar graph.
- SPNone.3dm.hl.TZ0.2c: Explain what feature of G enables you to state that it has an Eulerian trail and write down a...
- SPNone.3dm.hl.TZ0.2d: Explain what feature of G enables you to state it does not have an Eulerian circuit.
- SPNone.3dm.hl.TZ0.4a: Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling...
- SPNone.3dm.hl.TZ0.4b: (i) Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph...
- SPNone.3dm.hl.TZ0.5b: The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation...
- 10M.3dm.hl.TZ0.1a: (i) One version of Fermat’s little theorem states that, under certain...
- 10M.3dm.hl.TZ0.2: A graph G with vertices A, B, C, D, E has the following cost adjacency...
- 10M.3dm.hl.TZ0.5: Given that \(a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}\), show...
- 10M.3dm.hl.TZ0.1b: Find the general solution to the simultaneous congruences \[x \equiv 3(\bmod...
- 10M.3dm.hl.TZ0.3: The positive integer N is expressed in base 9 as \({({a_n}{a_{n - 1}} \ldots...
- 10M.3dm.hl.TZ0.4: (a) Show that, for a connected planar graph, \[v + f - e = 2.\] (b) Assuming that...
- 10N.3dm.hl.TZ0.1b: (i) A graph is simple, planar and connected. Write down the inequality connecting v and...
- 10N.3dm.hl.TZ0.4: (a) Write down Fermat’s little theorem. (b) In base 5 the representation of a...
- 10N.3dm.hl.TZ0.2: (a) Find the general solution for the following system of congruences. ...
- 10N.3dm.hl.TZ0.3: Consider the following weighted graph. (a) (i) Use Kruskal’s algorithm to...
- 10N.3dm.hl.TZ0.5a: A graph has n vertices with degrees 1, 2, 3, …, n. Prove that \(n \equiv 0(\bmod 4)\) or...
- 13M.3dm.hl.TZ0.1b: (i) Find the general solution to the diophantine equation \(332x - 99y = 1\). (ii) ...
- 13M.3dm.hl.TZ0.2b: (i) Use Dijkstra’s algorithm to find the path of minimum total weight joining A to...
- 13M.3dm.hl.TZ0.5a: Show that \(\sum\limits_{k = 1}^p {{k^p} \equiv 0(\bmod p)} \).
- 13M.3dm.hl.TZ0.5b: Given that \(\sum\limits_{k = 1}^p {{k^{p - 1}} \equiv n(\bmod p)} \) where...
- 13M.3dm.hl.TZ0.1a: Using the Euclidean algorithm, show that \(\gcd (99,{\text{ }}332) = 1\).
- 13M.3dm.hl.TZ0.2a: (i) Explain briefly why the graph contains an Eulerian trail but not an Eulerian...
- 13M.3dm.hl.TZ0.3a: By writing down an appropriate polynomial equation, determine the value of n.
- 13M.3dm.hl.TZ0.3b: Rewrite the above equation with numbers in base 7.
- 11N.3dm.hl.TZ0.1a: The vertices of a graph L are A, B, C, D, E, F, G and H. The weights of the edges in L are...
- 11N.3dm.hl.TZ0.2a: Use the Euclidean algorithm to find \(\gcd (752,{\text{ }}352)\).
- 11N.3dm.hl.TZ0.3a: In any graph, show that (i) the sum of the degrees of all the vertices is even; (ii) ...
- 11N.3dm.hl.TZ0.3b: Consider the following graph, M. (i) Show that M is planar. (ii) Explain why M is...
- 11N.3dm.hl.TZ0.4: Anna is playing with some cars and divides them into three sets of equal size. However, when...
- 11N.3dm.hl.TZ0.5a: Use the above result to show that if p is prime then \({a^p} \equiv a(\bmod p)\) where a is...
- 11N.3dm.hl.TZ0.5c: (i) State the converse of the result in part (a). (ii) Show that this converse is...
- 11N.3dm.hl.TZ0.2b: A farmer spends £8128 buying cows of two different breeds, A and B, for her farm. A cow of...
- 11N.3dm.hl.TZ0.5b: Show that \({2^{341}} \equiv 2(\bmod 341)\).
- 10N.3dm.hl.TZ0.5b: Let G be a simple graph with n vertices, \(n \geqslant 2\). Prove, by contradiction, that at...
- 09M.3dm.hl.TZ0.3: The adjacency table of the graph G , with vertices P, Q, R, S, T is given by: (a) ...
- 14M.3dm.hl.TZ0.1a: Draw the graph \(K\).
- 14M.3dm.hl.TZ0.2a: Consider the integers \(a = 871\) and \(b= 1157\), given in base \(10\). (i) Express...
- 14M.3dm.hl.TZ0.2d: Consider the set \(P\) of numbers of the form \({n^2} - n + 41,{\text{ }}n \in...
- 14M.3dm.hl.TZ0.3: (a) Draw a spanning tree for (i) the complete graph, \({K_4}\); ...
- 14M.3dm.hl.TZ0.1c: By removing customer A, use the method of vertex deletion, to determine a lower bound to the...
- 14M.3dm.hl.TZ0.2b: A list \(L\) contains \(n+ 1\) distinct positive integers. Prove that at least two members of...
- 14M.3dm.hl.TZ0.2c: Consider the simultaneous equations \(4x + y + 5z = a\) \(2x + z = b\) ...
- 14M.3dm.hl.TZ0.4: (a) (i) Write down the general solution of the recurrence relation...
- 13N.3dm.hl.TZ0.1: The following diagram shows a weighted graph. (a) Use Kruskal’s algorithm to find a...
- 13N.3dm.hl.TZ0.2: The following figure shows the floor plan of a museum. (a) (i) Draw a graph G...
- 13N.3dm.hl.TZ0.4a: Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\),...
- 13N.3dm.hl.TZ0.4e: Show that the lower bound found in (d) cannot be the length of an optimal solution for the...
- 13N.3dm.hl.TZ0.5a: Show that \(30\) is a factor of \({n^5} - n\) for all \(n \in \mathbb{N}\).
- 13N.3dm.hl.TZ0.5b: (i) Show that \({3^{{3^m}}} \equiv 3({\text{mod}}4)\) for all \(m \in \mathbb{N}\). (ii)...
- 13N.3dm.hl.TZ0.3: Consider an integer \(a\) with \((n + 1)\) digits written as...
- 14M.3dm.hl.TZ0.1b: Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to...
- 13N.3dm.hl.TZ0.4b: State an upper bound for the travelling salesman problem for graph \(G\).
- 13N.3dm.hl.TZ0.4d: Hence find a lower bound for the travelling salesman problem for \(G\).
- 15M.3dm.hl.TZ0.1a: The weights of the edges of a graph \(H\) are given in the following table. (i) Draw...
- 15M.3dm.hl.TZ0.2a: Draw \({K_{2,{\text{ }}2}}\) as a planar graph.
- 15M.3dm.hl.TZ0.2c: Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).
- 15M.3dm.hl.TZ0.4c: Draw an example of a simple connected planar graph on \(6\) vertices each of degree \(3\).
- 15M.3dm.hl.TZ0.5a: State the Fundamental theorem of arithmetic for positive whole numbers greater than \(1\).
- 15M.3dm.hl.TZ0.5b: Use the Fundamental theorem of arithmetic, applied to \(5577\) and \(99\,099\), to calculate...
- 15M.3dm.hl.TZ0.1b: Consider the following weighted graph. (i) Write down a solution to the Chinese postman...
- 15M.3dm.hl.TZ0.3a: The sequence \(\{ {u_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation...
- 15M.3dm.hl.TZ0.1c: (i) State the travelling salesman problem. (ii) Explain why there is no solution to...
- 15M.3dm.hl.TZ0.2b: Draw a spanning tree for \({K_{2,{\text{ }}2}}\).
- 15M.3dm.hl.TZ0.2d: Show that the complement of any complete bipartite graph does not possess a spanning tree.
- 15M.3dm.hl.TZ0.3b: The sequence \(\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation...
- 15M.3dm.hl.TZ0.3c: The sequence \(\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation...
- 15M.3dm.hl.TZ0.4a: (i) Show that \(2e \ge 3f{\text{ if }}v > 2\). (ii) Hence show that \({K_5}\),...
- 15M.3dm.hl.TZ0.4b: (i) State the handshaking lemma. (ii) Determine the value of \(f\), if each vertex...
- 15M.3dm.hl.TZ0.5c: Prove that \(\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m\) for all...
- 14N.3dm.hl.TZ0.1c: Explain why \(f(n)\) is always exactly divisible by \(5\).
- 14N.3dm.hl.TZ0.1d: By factorizing \(f(n)\) explain why it is always exactly divisible by \(6\).
- 14N.3dm.hl.TZ0.1e: Determine the values of \(n\) for which \(f(n)\) is exactly divisible by \(60\).
- 14N.3dm.hl.TZ0.2a: Use the pigeon-hole principle to prove that for any simple graph that has two or more...
- 14N.3dm.hl.TZ0.1a: Find the values of \(f(3)\), \(f(4)\) and \(f(5)\).
- 14N.3dm.hl.TZ0.1b: Use the Euclidean algorithm to find (i) \(\gcd \left( {f(3),{\text{ }}f(4)}...
- 14N.3dm.hl.TZ0.2c: Explain why each person cannot have shaken hands with exactly nine other people.
- 14N.3dm.hl.TZ0.3a: Use Dijkstra’s algorithm to find the cheapest route between \(A\) and \(J\), and state its cost.
- 14N.3dm.hl.TZ0.3b: For the remainder of the question you may find the cheapest route between any two towns by...
- 14N.3dm.hl.TZ0.4b: Find the remainder when \({41^{82}}\) is divided by 11.
- 14N.3dm.hl.TZ0.4c: Using your answers to parts (a) and (b) find the remainder when \({41^{82}}\) is divided by...
- 14N.3dm.hl.TZ0.5a: State the value of \({u_1}\).
- 14N.3dm.hl.TZ0.2b: Seventeen people attend a meeting. Each person shakes hands with at least one other person...
- 14N.3dm.hl.TZ0.5d: After they have played many games, Pat comes to watch. Use your answer from part (c) to...
- 14N.3dm.hl.TZ0.4a: Solve, by any method, the following system of linear congruences ...
- 14N.3dm.hl.TZ0.5b: Show that \({u_n}\) satisfies the recurrence...
- 14N.3dm.hl.TZ0.5c: Solve this recurrence relation to find the probability that Andy wins the...