• 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$.