DP Mathematics HL Questionbank
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.
| Path: |
Description
[N/A]Directly related questions
- 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...
- 18M.3dm.hl.TZ0.3b.i: In the context of graph theory, state the handshaking lemma.
- 18M.3dm.hl.TZ0.3a.iii: Draw \({\kappa _{3,\,2}}\) and explain why it does not have a Hamiltonian cycle.
- 18M.3dm.hl.TZ0.3a.ii: Show that \({\kappa _{3,\,3}}\) has a Hamiltonian cycle.
- 18M.3dm.hl.TZ0.3a.i: Draw \({\kappa _{3,\,3}}\).
- 16M.3dm.hl.TZ0.5c: show that \({v^2} - 13v + 24 \leqslant 0\) and hence determine the maximum possible value of \(v\).
- 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.5a: Show that the number of edges in \(G'\), the complement of \(G\), is...
- 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,...
- 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.
- 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...
