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