Question 10 of 12: Graph Theory — Paths, Planarity, Algorithms, Colouring
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Examination, 04-BS-16 Discrete Mathematics, May 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, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.
Approach. Each sub-part is a definitional or short-justification graph-theory question; part (c) additionally uses the edge-count bound for bipartite planar graphs.
(a) Definitions. An Euler path is a path (walk with no repeated edges) that traverses every EDGE of the graph exactly once (vertices may be revisited). A Hamilton path is a path that visits every VERTEX of the graph exactly once (edges need not all be used). $\boxed{\text{Euler} = \text{every edge once}; \text{Hamilton} = \text{every vertex once.}}$
(b) Existence condition for an Euler path $u\to v$ ($u\ne v$). A simple connected graph has an Euler path between two distinct vertices $u$ and $v$ if and only if $\boxed{u \text{ and } v \text{ are exactly the two vertices of odd degree, and every other vertex has even degree}}$ (an Euler circuit, by contrast, needs ALL vertices to have even degree).
(c) Planarity of $K_{2,3}$. $K_{2,3}$ has $V=5$ vertices and $E=2\times3=6$ edges. For a bipartite graph (no odd cycles, so no triangles, girth $\ge4$), planarity requires $E\le2V-4$; here $2(5)-4=6$, and $E=6$ satisfies this with equality. $K_{2,3}$ is in fact one of the standard planar bipartite graphs: draw the 2 left vertices $a,b$ and route the 3 right vertices $x,y,z$ as three parallel "theta" arcs from $a$ to $b$ (via $x$, via $y$, via $z$) — no edges need to cross. $\boxed{K_{2,3}\text{ IS planar.}}$
(d) Dijkstra's algorithm. Dijkstra's algorithm solves the $\boxed{\text{single-source shortest-path problem}}$: given a weighted graph with non-negative edge weights and a source vertex, it computes the minimum total-weight path from the source to every other vertex.
(e) Chromatic number of $K_6$. In a complete graph every pair of vertices is adjacent, so every vertex needs a colour distinct from every other vertex's colour: $\chi(K_n)=n$. $\boxed{\chi(K_6)=6.}$
Final results — Question 10
Part
Result
(a)
Euler path = every edge once; Hamilton path = every vertex once
(b)
Exactly $u,v$ have odd degree, all other vertices even
(c)
$K_{2,3}$ is planar ($E=6=2V-4$, drawable without crossings)
