• Syllabus

Topic 10 - Option: Discrete mathematics

---

---

Sub sections and their related questions

10.1

• SPNone.3dm.hl.TZ0.5b: The sequence \(\{ {v_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation...
• 14M.3dm.hl.TZ0.2b: A list \(L\) contains \(n+ 1\) distinct positive integers. Prove that at least two members of...
• 14N.3dm.hl.TZ0.2a: Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices...
• 14N.3dm.hl.TZ0.2b: Seventeen people attend a meeting. Each person shakes hands with at least one other person and...
• 18M.3dm.hl.TZ0.5b: It is known that \({\alpha ^2} = \alpha  + 1\) where \(\alpha  = \frac{{1 + \sqrt 5 }}{2}\). For...

10.2

• 12M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where...
• 12N.3dm.hl.TZ0.3a: Using the Euclidean algorithm, find h .
• 12N.3dm.hl.TZ0.3b: Hence find integers A and B such that 861A + 957B = h .
• 08M.3dm.hl.TZ1.1: Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315. Hence state...
• 08M.3dm.hl.TZ2.1: (a)     Use the Euclidean algorithm to find the gcd of 324 and 129. (b)     Hence show that...
• 08N.3dm.hl.TZ0.1b: (i)     Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and...
• 08N.3dm.hl.TZ0.3a: Write 57128 as a product of primes.
• 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.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 have...
• 09M.3dm.hl.TZ0.2: (a)     Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) . (b)     Hence give the...
• SPNone.3dm.hl.TZ0.1a: Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.
• 13M.3dm.hl.TZ0.1a: Using the Euclidean algorithm, show that \(\gcd (99,{\text{ }}332) = 1\).
• 11N.3dm.hl.TZ0.2a: Use the Euclidean algorithm to find \(\gcd (752,{\text{ }}352)\).
• 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 \mathbb{N}\). (i)...
• 13N.3dm.hl.TZ0.5a: Show that \(30\) is a factor of \({n^5} - n\) for all \(n \in \mathbb{N}\).
• 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)} \right)\); (ii)...
• 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\).
• 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.5c: Prove that \(\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m\) for all...
• 16M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.
• 17M.3dm.hl.TZ0.1a: Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.
• 17M.3dm.hl.TZ0.1c: By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest common...
• 18M.3dm.hl.TZ0.4a: Show that...
• 18M.3dm.hl.TZ0.4b.i: State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for odd positive integers \(k\).
• 18M.3dm.hl.TZ0.4b.ii: State the value of \({\text{gcd}}\left( {4k + 2,\,3k + 1} \right)\) for even positive...

10.3

• 12N.3dm.hl.TZ0.3d: Find the general solution to the diophantine equation \(861x + 957y = 6\) .
• 08M.3dm.hl.TZ1.1: Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315. Hence state...
• 08M.3dm.hl.TZ2.1: (a)     Use the Euclidean algorithm to find the gcd of 324 and 129. (b)     Hence show that...
• 11M.3dm.hl.TZ0.1b: (i)     Find the general solution to the diophantine equation \(56x + 315y = 21\). (ii)    ...
• 09M.3dm.hl.TZ0.2: (a)     Use the Euclidean algorithm to find gcd(\(12\,306\), 2976) . (b)     Hence give the...
• 09N.3dm.hl.TZ0.1: An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has...
• SPNone.3dm.hl.TZ0.1b: Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .
• 13M.3dm.hl.TZ0.1b: (i)     Find the general solution to the diophantine equation \(332x - 99y = 1\). (ii)    ...
• 11N.3dm.hl.TZ0.2b: A farmer spends £8128 buying cows of two different breeds, A and B, for her farm. A cow of breed...
• 15N.3dm.hl.TZ0.3a: Show that there are exactly two solutions to the equation \(1982 = 36a + 74b\), with...
• 17M.3dm.hl.TZ0.1b.i: Hence, or otherwise, find the general solution of the Diophantine equation \[264x - 1365y = 3.\]
• 17M.3dm.hl.TZ0.1b.ii: Hence find the general solution of the Diophantine equation \[264x - 1365y = 6.\]

10.4

• 12M.3dm.hl.TZ0.1b: Find the least positive solution of \(123x \equiv 1(\bmod 2347)\) .
• 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.5a: Use the result \(2003 = 6 \times 333 + 5\) and Fermat’s little theorem to show that...
• 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 1001)\), noting...
• 12N.3dm.hl.TZ0.3c: Using part (b), solve \(287w \equiv 2(\bmod 319\)) , where...
• 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.TZ2.3a: (i)     Given that \(a \equiv d(\bmod n)\) and \(b \equiv c(\bmod n)\) prove...
• 08N.3dm.hl.TZ0.1c: In each of the following cases find the solutions, if any, of the given linear congruence. (i)  ...
• 11M.3dm.hl.TZ0.1b: (i)     Find the general solution to the diophantine equation \(56x + 315y = 21\). (ii)    ...
• 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}\) .
• 09M.3dm.hl.TZ0.4: Two mathematicians are planning their wedding celebration and are trying to arrange the seating...
• SPNone.3dm.hl.TZ0.3b: Find all the integers between 100 and 200 satisfying the simultaneous congruences...
• 10M.3dm.hl.TZ0.1b: Find the general solution to the simultaneous congruences \[x \equiv 3(\bmod...
• 10M.3dm.hl.TZ0.5: Given that \(a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}\), show...
• 10N.3dm.hl.TZ0.2: (a)     Find the general solution for the following system of congruences.     ...
• 13M.3dm.hl.TZ0.1b: (i)     Find the general solution to the diophantine equation \(332x - 99y = 1\). (ii)    ...
• 11N.3dm.hl.TZ0.4: Anna is playing with some cars and divides them into three sets of equal size. However, when she...
• 14M.3dm.hl.TZ0.2c: Consider the simultaneous equations      \(4x + y + 5z = a\)      \(2x + z = b\)     ...
• 13N.3dm.hl.TZ0.5b: (i)     Show that \({3^{{3^m}}} \equiv 3({\text{mod}}4)\) for all \(m \in \mathbb{N}\). (ii)    ...
• 14N.3dm.hl.TZ0.4a: Solve, by any method, the following system of linear congruences      \(x \equiv 9(\bmod...
• 14N.3dm.hl.TZ0.4c: Using your answers to parts (a) and (b) find the remainder when \({41^{82}}\) is divided by \(55\).
• 15N.3dm.hl.TZ0.3b: Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).
• 15N.3dm.hl.TZ0.5a: Given a sequence of non negative integers \(\{ {a_r}\} \) show that (i)    ...
• 15N.3dm.hl.TZ0.5b: Hence determine whether the base \(3\) number \(22010112200201\) is divisible by \(8\).
• 17N.3dm.hl.TZ0.4a: With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees a...
• 17N.3dm.hl.TZ0.4b: Hence or otherwise, find the general solution to the above system of linear congruences.
• 18M.3dm.hl.TZ0.2b.ii: Hence solve the linear congruence \(5x \equiv 7\left( {{\text{mod}}\,13} \right)\).

10.5

• 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.
• 08N.3dm.hl.TZ0.1a: Convert the decimal number 51966 to base 16.
• 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 its...
• 09N.3dm.hl.TZ0.4a: Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is...
• 09N.3dm.hl.TZ0.4b: The representation of the positive integer N in base p is denoted by \({(N)_p}\) . If...
• 10M.3dm.hl.TZ0.3: The positive integer N is expressed in base 9 as \({({a_n}{a_{n - 1}} \ldots {a_0})_9}\). (a)  ...
• 10N.3dm.hl.TZ0.4: (a)     Write down Fermat’s little theorem. (b)     In base 5 the representation of a natural...
• 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.
• 14M.3dm.hl.TZ0.2a: Consider the integers \(a = 871\) and \(b= 1157\), given in base \(10\). (i)     Express...
• 13N.3dm.hl.TZ0.3: Consider an integer \(a\) with \((n + 1)\) digits written as...
• 15N.3dm.hl.TZ0.5b: Hence determine whether the base \(3\) number \(22010112200201\) is divisible by \(8\).
• 16M.3dm.hl.TZ0.3a: (i)     Given that \({(43)_n} \times {(56)_n} = {(3112)_n}\), show that...
• 16M.3dm.hl.TZ0.3b: Determine the set of values of \(n\) satisfying \({(13)_n} \times {(21)_n} = {(273)_n}\).
• 16M.3dm.hl.TZ0.3c: Show that there are no possible values of \(n\) satisfying...
• 16N.3dm.hl.TZ0.1a: (i)     By converting the base 7 number to base 10, find the value of \(x\), in base 10. (ii)  ...
• 16N.3dm.hl.TZ0.1b: Let \(y\) be the base 9 number \({({a_n}{a_{n - 1}} \ldots {a_1}{a_0})_9}\). Show that \(y\) is...
• 16N.3dm.hl.TZ0.1c: Using the method from part (b), find the unit digit when the base 9 number \({(321321321)_9}\) is...
• 17N.3dm.hl.TZ0.5a: Convert the decimal number 1071 to base 12.
• 17N.3dm.hl.TZ0.5b: Write the decimal number 1071 as a product of its prime factors.
• 17N.3dm.hl.TZ0.5c.i: Using your answers to part (a) and (b), prove that there is only one possible value for \(b\) and...
• 17N.3dm.hl.TZ0.5c.ii: Hence state the value of \(a\).

10.6

• 12M.3dm.hl.TZ0.5a: Use the result \(2003 = 6 \times 333 + 5\) and Fermat’s little theorem to show that...
• 12M.3dm.hl.TZ0.5b: Find \({2^{2003}}(\bmod 11)\) and \({2^{2003}}(\bmod 13)\).
• 12N.3dm.hl.TZ0.4a: State Fermat’s little theorem.
• 08M.3dm.hl.TZ2.3b: Show that \({x^{97}} - x + 1 \equiv 0(\bmod 97)\) has no solution.
• 08N.3dm.hl.TZ0.3c: Prove that \(\left. {22} \right|{5^{11}} + {17^{11}}\).
• 09M.3dm.hl.TZ0.5: (a)     Using Fermat’s little theorem, show that, in base 10, the last digit of n is always equal...
• 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.3a: One version of Fermat’s little theorem states that, under certain conditions,...
• 10M.3dm.hl.TZ0.1a: (i)     One version of Fermat’s little theorem states that, under certain...
• 10N.3dm.hl.TZ0.4: (a)     Write down Fermat’s little theorem. (b)     In base 5 the representation of a natural...
• 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...
• 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 any...
• 11N.3dm.hl.TZ0.5b: Show that \({2^{341}} \equiv 2(\bmod 341)\).
• 11N.3dm.hl.TZ0.5c: (i)     State the converse of the result in part (a). (ii)     Show that this converse is not true.
• 14N.3dm.hl.TZ0.1c: Explain why \(f(n)\) is always exactly divisible by \(5\).
• 14N.3dm.hl.TZ0.4b: Find the remainder when \({41^{82}}\) is divided by 11.
• 15N.3dm.hl.TZ0.3b: Hence, or otherwise, find the remainder when \({1982^{1982}}\) is divided by \(37\).
• 17N.3dm.hl.TZ0.2b: For every prime number \(p > 3\), show that \(p|{u_{p - 1}}\).
• 18M.3dm.hl.TZ0.2a: State Fermat’s little theorem.
• 18M.3dm.hl.TZ0.2b.i: Use Fermat’s little theorem to show that \(x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)\).

10.7

• 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.4b: A simple graph G has v vertices and e edges. The complement \(G'\) of G has \({e'}\) edges. (i)...
• 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 the...
• 08M.3dm.hl.TZ1.4c: List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles...
• 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.2b: Show that a graph cannot have exactly one vertex of odd degree.
• 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.4: (a)     A connected planar graph G has e edges and v vertices. (i)     Prove that...
• 09N.3dm.hl.TZ0.3a: The planar graph G and its complement \(G'\) are both simple and connected. Given that G has 6...
• 09N.3dm.hl.TZ0.5: Show that a graph is bipartite if and only if it contains only cycles of even length.
• SPNone.3dm.hl.TZ0.2a: Draw the graph G as a planar graph.
• 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...
• 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 e,...
• 10N.3dm.hl.TZ0.5a: A graph has n vertices with degrees 1, 2, 3, …, n. Prove that \(n \equiv 0(\bmod 4)\) or...
• 10N.3dm.hl.TZ0.5b: Let G be a simple graph with n vertices, \(n \geqslant 2\). Prove, by contradiction, that at...
• 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 given...
• 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 not...
• 14M.3dm.hl.TZ0.1a: Draw the graph \(K\).
• 14M.3dm.hl.TZ0.3: (a)     Draw a spanning tree for           (i)     the complete graph, \({K_4}\);          ...
• 13N.3dm.hl.TZ0.2: The following figure shows the floor plan of a museum.   (a)     (i)     Draw a graph G that...
• 14N.3dm.hl.TZ0.2a: Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices...
• 14N.3dm.hl.TZ0.2b: Seventeen people attend a meeting. Each person shakes hands with at least one other person and...
• 14N.3dm.hl.TZ0.2c: Explain why each person cannot have shaken hands with exactly nine other people.
• 15M.3dm.hl.TZ0.1a: The weights of the edges of a graph \(H\) are given in the following table. (i)     Draw the...
• 15M.3dm.hl.TZ0.2a: Draw \({K_{2,{\text{ }}2}}\) as a planar graph.
• 15M.3dm.hl.TZ0.2b: Draw a spanning tree for \({K_{2,{\text{ }}2}}\).
• 15M.3dm.hl.TZ0.2c: Draw the graph of the complement of \({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.4a: (i)     Show that \(2e \ge 3f{\text{ if }}v > 2\). (ii)     Hence show that \({K_5}\), the...
• 15M.3dm.hl.TZ0.4b: (i)     State the handshaking lemma. (ii)     Determine the value of \(f\), if each vertex has...
• 15M.3dm.hl.TZ0.4c: Draw an example of a simple connected planar graph on \(6\) vertices each of degree \(3\).
• 15N.3dm.hl.TZ0.4a: Show that \(G\) is bipartite.
• 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.4c: In a planar graph the degree of a face is defined as the number of edges adjacent to that...
• 15N.3dm.hl.TZ0.4d: \(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\) vertices...
• 15N.3dm.hl.TZ0.4e: Hence prove that for \(H\) (i)     \(e \ge 2f\); (ii)     \(e \le 2v - 4\).
• 15N.3dm.hl.TZ0.4f: Hence prove that \({K_{3,{\text{ }}3}}\) is not planar.
• 16M.3dm.hl.TZ0.5a: Show that the number of edges in \(G'\), the complement of \(G\), is...
• 16M.3dm.hl.TZ0.5b: show that the sum of the number of faces in \(G\) and the number of faces in \(G'\) is...
• 16M.3dm.hl.TZ0.5c: show that \({v^2} - 13v + 24 \leqslant 0\) and hence determine the maximum possible value of \(v\).
• 16N.3dm.hl.TZ0.2a: a graph cannot exist with a degree sequence of...
• 16N.3dm.hl.TZ0.2b: a simple, connected, planar graph cannot exist with a degree sequence of...
• 16N.3dm.hl.TZ0.2c: a tree cannot exist with a degree sequence of...
• 17N.3dm.hl.TZ0.3a.i: Draw the complete bipartite graph \({\kappa _{3,3}}\).
• 17N.3dm.hl.TZ0.3a.ii: Prove that \({\kappa _{3,3}}\) is not planar.
• 17N.3dm.hl.TZ0.3b: A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning tree...
• 17N.3dm.hl.TZ0.3c: If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the probability...
• 18M.3dm.hl.TZ0.3a.i: Draw \({\kappa _{3,\,3}}\).
• 18M.3dm.hl.TZ0.3a.ii: Show that \({\kappa _{3,\,3}}\) has a Hamiltonian cycle.
• 18M.3dm.hl.TZ0.3a.iii: Draw \({\kappa _{3,\,2}}\) and explain why it does not have a Hamiltonian cycle.
• 18M.3dm.hl.TZ0.3b.i: In the context of graph theory, state the handshaking lemma.
• 18M.3dm.hl.TZ0.3c: Let T be a tree with \(v\) where \(v\) ≥ 2. Use the handshaking lemma to prove that T has at...

10.8

• 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.
• 12N.3dm.hl.TZ0.1b: (i)     Does this graph have an Eulerian circuit? Justify your answer. (ii)     Does this graph...
• 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 the...
• 08M.3dm.hl.TZ1.4c: List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles...
• 08M.3dm.hl.TZ2.2a: The table below shows the distances between towns A, B, C, D and E.     (i)     Draw the...
• 11M.3dm.hl.TZ0.4a: (i)     Determine if any Hamiltonian cycles exist in G . If so, write one down. Otherwise,...
• 09M.3dm.hl.TZ0.3: The adjacency table of the graph G , with vertices P, Q, R, S, T is given by:     (a)    ...
• 09N.3dm.hl.TZ0.2a + c: (a)     (i)     What feature of the graph enables you to deduce that G contains an Eulerian...
• SPNone.3dm.hl.TZ0.2c: Explain what feature of G enables you to state that it has an Eulerian trail and write down a trail.
• SPNone.3dm.hl.TZ0.2d: Explain what feature of G enables you to state it does not have an Eulerian circuit.
• 13M.3dm.hl.TZ0.2a: (i)     Explain briefly why the graph contains an Eulerian trail but not an Eulerian...
• 11N.3dm.hl.TZ0.3b: Consider the following graph, M. (i)     Show that M is planar. (ii)     Explain why M is not...
• 13N.3dm.hl.TZ0.2: The following figure shows the floor plan of a museum.   (a)     (i)     Draw a graph G that...
• 13N.3dm.hl.TZ0.4a: Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\),...
• 15N.3dm.hl.TZ0.1b: Visitors to Switzerland can visit some principal locations for tourism by using a network of...
• 17M.3dm.hl.TZ0.3a.i: In the context of graph theory, explain briefly what is meant by a circuit;
• 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.3b: The graph \(G\) has six vertices and an Eulerian circuit. Determine whether or not its complement...
• 17M.3dm.hl.TZ0.3c: Find an example of a graph \(H\), with five vertices, such that \(H\) and its complement \(H'\)...
• 18M.3dm.hl.TZ0.1a.i: State what feature of G ensures that G has an Eulerian trail.
• 18M.3dm.hl.TZ0.1a.ii: State what feature of G ensures that G does not have an Eulerian circuit.
• 18M.3dm.hl.TZ0.1b: Write down an Eulerian trail in G.

10.9

• 12N.3dm.hl.TZ0.1a: Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T ....
• 08M.3dm.hl.TZ1.5a: The weighted graph H is shown below.   Use Kruskal’s Algorithm, indicating the order in which...
• 08N.3dm.hl.TZ0.2a: Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and...
• 08N.3dm.hl.TZ0.2b: Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph...
• 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 possible...
• 09N.3dm.hl.TZ0.2a + c: (a)     (i)     What feature of the graph enables you to deduce that G contains an Eulerian...
• SPNone.3dm.hl.TZ0.4b: (i)     Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph...
• 10M.3dm.hl.TZ0.2: A graph G with vertices A, B, C, D, E has the following cost adjacency...
• 10N.3dm.hl.TZ0.3: Consider the following weighted graph.     (a)     (i)     Use Kruskal’s algorithm to find...
• 13M.3dm.hl.TZ0.2b: (i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D. (ii)  ...
• 13N.3dm.hl.TZ0.1: The following diagram shows a weighted graph.   (a)     Use Kruskal’s algorithm to find a...
• 14N.3dm.hl.TZ0.3a: Use Dijkstra’s algorithm to find the cheapest route between \(A\) and \(J\), and state its cost.
• 15M.3dm.hl.TZ0.1a: The weights of the edges of a graph \(H\) are given in the following table. (i)     Draw the...
• 15N.3dm.hl.TZ0.1a: The distances by road, in kilometres, between towns in Switzerland are shown in the following...
• 16M.3dm.hl.TZ0.2a: Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling...
• 16M.3dm.hl.TZ0.2b: By first removing A , use the deleted vertex algorithm to find a lower bound for the travelling...
• 16N.3dm.hl.TZ0.4a: (i)     Draw the graph \({\kappa _4}\) including the weights of all the edges. (ii)     Use the...
• 16N.3dm.hl.TZ0.4b: Consider the graph \({\kappa _5}\). Use the deleted vertex algorithm, with \({{\text{A}}_5}\) as...
• 16N.3dm.hl.TZ0.4c: (i)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a...
• 16N.3dm.hl.TZ0.4d: By splitting the weight of the edge \({{\text{A}}_i}{{\text{A}}_j}\) into two parts or otherwise,...

10.10

• 12N.3dm.hl.TZ0.1c: The graph above is now to be considered with the edges representing roads in a town and with the...
• 08M.3dm.hl.TZ2.2a: The table below shows the distances between towns A, B, C, D and E.     (i)     Draw the...
• 11M.3dm.hl.TZ0.2a: By first finding a minimum spanning tree on the subgraph of H formed by deleting vertex A and all...
• 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?
• 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...
• 10M.3dm.hl.TZ0.2: A graph G with vertices A, B, C, D, E has the following cost adjacency...
• 14M.3dm.hl.TZ0.1c: By removing customer A, use the method of vertex deletion, to determine a lower bound to the...
• 13N.3dm.hl.TZ0.4e: Show that the lower bound found in (d) cannot be the length of an optimal solution for the...
• 14M.3dm.hl.TZ0.1b: Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to the...
• 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\).
• 14N.3dm.hl.TZ0.3b: For the remainder of the question you may find the cheapest route between any two towns by...
• 15M.3dm.hl.TZ0.1b: Consider the following weighted graph. (i) Write down a solution to the Chinese postman...
• 15M.3dm.hl.TZ0.1c: (i)     State the travelling salesman problem. (ii)     Explain why there is no solution to the...
• 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.2b: By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm...
• 17N.3dm.hl.TZ0.1a: Draw the weighted graph \(H\).
• 17N.3dm.hl.TZ0.1b: Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s...
• 17N.3dm.hl.TZ0.1c: By first removing library C, use the deleted vertex algorithm, to find a lower bound for...
• 18M.3dm.hl.TZ0.1c.i: State the Chinese postman problem.
• 18M.3dm.hl.TZ0.1c.ii: Starting and finishing at B, find a solution to the Chinese postman problem for G.
• 18M.3dm.hl.TZ0.1c.iii: Calculate the total weight of the solution.

10.11

• SPNone.3dm.hl.TZ0.5a: The sequence \(\{ {u_n}\} \) , \(n \in {\mathbb{Z}^ + }\) , satisfies the recurrence relation...
• 14M.3dm.hl.TZ0.4: (a)     (i)     Write down the general solution of the recurrence relation...
• 14N.3dm.hl.TZ0.5a: State the value of \({u_1}\).
• 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 \({n^{{\text{th}}}}\)...
• 14N.3dm.hl.TZ0.5d: After they have played many games, Pat comes to watch. Use your answer from part (c) to estimate...
• 15M.3dm.hl.TZ0.3a: The sequence \(\{ {u_n}\} ,{\text{ }}n \in \mathbb{N}\), satisfies the recurrence relation...
• 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...
• 15N.3dm.hl.TZ0.2a: Use the recurrence relation to find \({u_2}\).
• 15N.3dm.hl.TZ0.2b: Find an expression for \({u_n}\) in terms of \(n\).
• 15N.3dm.hl.TZ0.2c: A second recurrence relation, where \({v_1} = {u_1}\) and \({v_2} = {u_2}\), is given by...
• 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.4b: Use strong induction to prove that the solution to the recurrence relation...
• 16M.3dm.hl.TZ0.4c: Find a simplified expression for \({u_n} + {v_n}\) given that, (i)     \(n\) is even. (ii)    ...
• 16N.3dm.hl.TZ0.3a: Find the values of \({u_1},{\text{ }}{u_2},{\text{ }}{u_3}\).
• 16N.3dm.hl.TZ0.3b: Show that \({u_{n + 2}} = {u_{n + 1}} + {u_n}\).
• 16N.3dm.hl.TZ0.3c: (i)     Write down the auxiliary equation for this recurrence relation. (ii)     Hence find the...
• 16N.3dm.hl.TZ0.3d: (i)     Given that \(A = \frac{1}{{\sqrt 5 }}\left( {\frac{{1 + \sqrt 5 }}{2}} \right)\), use the...
• 16N.3dm.hl.TZ0.3e: Find the value of \({u_{20}}\).
• 16N.3dm.hl.TZ0.3f: Find the smallest value of \(n\) for which \({u_n} > 100\,000\).
• 17M.3dm.hl.TZ0.4a: Verify that the recurrence relation is satisfied by \[{u_n} = A{\alpha ^n} + B{\beta...
• 17M.3dm.hl.TZ0.4b: Solve the recurrence relation \({u_{n + 2}} - 2{u_{n + 1}} + 5{u_n} = 0\) given that...
• 17N.3dm.hl.TZ0.2a: Find an expression for \({u_n}\) in terms of \(n\).
• 18M.3dm.hl.TZ0.5a: Write down the auxiliary equation and use it to find an expression for \({f_n}\) in terms of \(n\).