DP Mathematics HL Questionbank

• Syllabus

10.7

Sub sections and their related questions

Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges.

• 12M.3dm.hl.TZ0.3a: Draw the graph G .
• 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.5b: (i)     A tree has v vertices. State the number of edges in the tree, justifying your...
• 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...
• 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.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...
• 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...
• 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...

Degree of a vertex, degree sequence.

• 12M.3dm.hl.TZ0.3a: Draw the graph G .
• 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.5b: (i)     A tree has v vertices. State the number of edges in the tree, justifying your...
• 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.3a: In any graph, show that (i)     the sum of the degrees of all the vertices is even; (ii)    ...
• 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...
• 15N.3dm.hl.TZ0.4c: In a planar graph the degree of a face is defined as the number of edges adjacent to that...

Handshaking lemma.

• 12M.3dm.hl.TZ0.3a: Draw the graph G .
• 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.TZ2.2b: Show that a graph cannot have exactly one vertex of odd degree.
• 11N.3dm.hl.TZ0.3a: In any graph, show that (i)     the sum of the degrees of all the vertices is even; (ii)    ...
• 14N.3dm.hl.TZ0.2c: Explain why each person cannot have shaken hands with exactly nine other people.
• 15M.3dm.hl.TZ0.4b: (i)     State the handshaking lemma. (ii)     Determine the value of $f$, if each vertex has...
• 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...
• 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...

Simple graphs; connected graphs; complete graphs; bipartite graphs; planar graphs; trees; weighted graphs, including tabular representation.

• 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.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...
• 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.
• 10M.3dm.hl.TZ0.4: (a)     Show that, for a connected planar graph, $$v + f - e = 2.$$ (b)     Assuming that...
• 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...
• 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...
• 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.2d: Show that the complement of any complete bipartite graph does not possess a spanning tree.
• 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.4d: $H$ is a simple connected planar bipartite graph with $e$ edges, $f$ faces, $v$ vertices...

Subgraphs; complements of graphs.

• 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)...
• 09N.3dm.hl.TZ0.3a: The planar graph G and its complement $G'$ are both simple and connected. Given that G has 6...
• 10M.3dm.hl.TZ0.4: (a)     Show that, for a connected planar graph, $$v + f - e = 2.$$ (b)     Assuming that...
• 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.

Euler’s relation: $v - e + f = 2$ ; theorems for planar graphs including $e \leqslant 3v - 6$ , $e \leqslant 2v - 4$ , leading to the results that ${\kappa _5}$ and ${\kappa _{3,3}}$ are not planar.

• 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.TZ2.5: (a)     (i)     Show that Euler’s relation $f - e + v = 2$ is valid for a spanning tree of...
• 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,...
• 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...
• 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$.
• 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...