Graph theory and combinatorics

Colouring, planarity, paths, and the difference between adjacent and connected.

6 questions. Reveal each answer when you have committed to one.

1. A graph’s chromatic number is the smallest number of colours such that no two ___ vertices share a colour.

   • Adistant
   • Blabelled
   • Cconnected
   • Dadjacent
   Show the answer

   D. adjacent

   Adjacent means joined by an edge; connected means joined by some path. Under the connected reading the answer for any connected graph would just be its vertex count — a path on five vertices would give 5 instead of the correct 2. More on chromatic number.

2. The four colour theorem states that four colours always suffice for

   • Aplanar graphs
   • Btrees
   • Ccomplete graphs
   • Devery graph
   Show the answer

   A. planar graphs

   It applies to graphs drawable in the plane without crossing edges, which is what makes it a statement about maps. Graphs in general need arbitrarily many colours. More on planar graph.

3. A graph is planar when

   • Ait has at most four vertices
   • Bsome drawing of it has no crossing edges
   • Cevery drawing of it has no crossing edges
   • Dit contains no cycles
   Show the answer

   B. some drawing of it has no crossing edges

   Planarity is a property of the graph, not of a particular picture. A planar graph is usually drawn with crossings; what matters is that a crossing-free drawing exists. More on planar graph.

4. If more items than containers are placed into containers, at least one container must hold two or more. Which principle states this?

   • AThe axiom of choice
   • BEuler’s formula
   • CThe pigeonhole principle
   • DRamsey’s theorem
   Show the answer

   C. The pigeonhole principle

   The strict inequality does all the work and no finiteness assumption is needed. Despite being immediate, it underpins a large number of proofs that show something exists without indicating where. More on pigeonhole principle.

5. A Hamiltonian path visits every

   • Aface exactly once
   • Bcycle exactly once
   • Cedge exactly once
   • Dvertex exactly once
   Show the answer

   D. vertex exactly once

   The path that visits every edge once is Eulerian instead, and the two behave completely differently: Eulerian paths have a simple degree criterion checkable in linear time. More on hamiltonian path.

6. Deciding whether a graph has a Hamiltonian path is

   • ANP-complete
   • Bundecidable
   • Ctrivial
   • Dsolvable in linear time
   Show the answer

   A. NP-complete

   This is the standard contrast with Eulerian paths, which are easy. Two problems that sound alike sit on opposite sides of the tractability line. More on hamiltonian path.