Graph Colouring and Planarity · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Color maps and test flat drawings

Mathematics · Discrete Mathematics · ages 21-22
Name ______________________   Date ____________

  1. A connected planar drawing has 8 vertices and 12 edges. How many faces does it have?

    Answer: ______________

  2. Vertices A, B, C, D form a ring where each vertex is joined to its neighbours in the ring. How many colors are needed if joined vertices must differ?

    • 2
    • 3
    • 4
    • 1

  3. Vertices A, B, C, D form a ring, each joined to its ring neighbours. How many colors are needed?

    • 2
    • 3
    • 4

  4. A connected planar drawing has 8 vertices and 12 edges. How many faces does it have?

    Answer: ______________

  5. A graph where every vertex has at most 3 neighbours can always be colored with 4 colors. True or false?

    Circle one:   True   False

  6. The complete graph on 5 vertices has 10 edges. Since a planar connected graph with 5 vertices has at most 9 edges, this graph cannot be planar. Is this reasoning correct?

    Circle one:   True   False

  7. A graph has maximum degree 4. The greedy bound is one plus the maximum degree. What is the greedy bound here?

    • 4
    • 6
    • 5
    • 3

  8. A graph has maximum degree 4. What is its greedy color bound?

    • 4
    • 6
    • 5

  9. The complete graph on five vertices has 10 edges. Why is it not planar?

    • It has too few edges to be drawn
    • It beats the edge cap, so it cannot lie flat
    • It needs exactly 4 colors to draw

  10. A bipartite connected planar graph has 6 vertices. The bipartite edge bound allows at most twice the vertices minus 4 edges. How many edges are allowed at most?

    Answer: ______________

LightMySky · lightmysky.comW1-mt_6xy6UPBppw-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Color maps and test flat drawings W1-mt_6xy6UPBppw-s1

  1. 6 · Euler relation gives faces equal to 2 minus vertices plus edges, which is 2 minus 8 plus 12, equal to 6.
  2. 2 · 2 colors suffice for the ring with four vertices. Color A and C with one color and B and D with another, so neighbours differ.
  3. 2 · Color opposite corners alike and neighbours still differ, so 2 suffices.
  4. 6 · Faces equal 2 minus 8 plus 12, which is 6.
  5. True · Each vertex meets at most 3 earlier neighbours, so a fourth color is always free.
  6. True · Planar bound is 3 times vertices minus 6, which is 9 for 5 vertices. With 10 edges, planarity is impossible.
  7. 5 · One plus 4 equals 5, so the greedy procedure guarantees a coloring with 5 colors.
  8. 5 · One plus 4 is 5, so greedy order guarantees a 5 coloring.
  9. It beats the edge cap, so it cannot lie flat · Five vertices allow at most 9 edges flat, but K5 carries 10, so crossings are forced.
  10. 8 · Twice 6 minus 4 equals 8, so at most 8 edges are possible.
Worksheet · LightMySky