NivaarExam PrepOfficial exam papers ↗

04-BS-16 · December 2013

Question 9 of 12: Graph Theory — Euler Paths and Planarity

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 9: Graph Theory — Euler Paths and Planarity (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $K_{2,3}$ (complete bipartite, parts of size 2 and 3); $K_{3,3}$; $K_4$; $K_5$ (complete graphs).

Find. (a) Euler-path existence for $K_{2,3}$ and the general condition. (b) Planarity of $K_{3,3}$, $K_4$, $K_5$.

  1. (a-i) Degrees in $K_{2,3}$. The 2 vertices on the small side each connect to all 3 on the other side: degree $3$ (odd) each. The 3 vertices on the large side each connect to both vertices on the small side: degree $2$ (even) each. So $K_{2,3}$ has exactly $\boxed{2\text{ odd-degree vertices}}$ (the two on the size-2 side).
  2. (a-i) Conclusion. A connected graph has an Euler path (not necessarily a circuit) iff it has exactly $0$ or $2$ odd-degree vertices. $K_{2,3}$ has exactly 2. $\boxed{\text{Yes, }K_{2,3}\text{ has an Euler path}}$ (starting and ending at the two odd-degree vertices; not an Euler circuit since it isn't 0).
  3. (a-ii) General condition. A connected graph has an Euler path iff it has $\boxed{\text{exactly 0 (Euler circuit) or exactly 2 vertices of odd degree}}$ (the path must start/end at the two odd vertices, if any).
  4. (b-a) $K_{3,3}$. $K_{3,3}$ is bipartite (no triangles), so if it were planar it would satisfy $|E|\le2|V|-4$. Here $|V|=6$, $|E|=3\times3=9$, but $2|V|-4=2(6)-4=8$, and $9>8$ violates the bound. $\boxed{\text{Non-planar}}$ (classical Kuratowski example; cannot be drawn without edge crossings).
  5. (b-b) $K_4$. $|V|=4,|E|=6$; the general planarity bound $|E|\le3|V|-6=6$ is met with equality, and $K_4$ can be drawn explicitly as a triangle with one vertex placed inside connected to all three corners, with no crossings. $\boxed{\text{Planar.}}$
  6. (b-c) $K_5$. $|V|=5,|E|=10$; the bound gives $3|V|-6=9<10=|E|$, so $K_5$ fails the necessary condition for planarity. $\boxed{\text{Non-planar}}$ (the other classical Kuratowski graph).
Final results — Question 9
PartResult
(a-i)Yes — $K_{2,3}$ has exactly 2 odd-degree vertices
(a-ii)Connected graph has Euler path iff 0 or 2 odd-degree vertices
(b-a) $K_{3,3}$Non-planar ($|E|=9>2|V|-4=8$)
(b-b) $K_4$Planar ($|E|=6=3|V|-6$)
(b-c) $K_5$Non-planar ($|E|=10>3|V|-6=9$)