Graphs, Degrees and the Handshake Lemma · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Graphs and the handshake lemma

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

  1. A graph has vertex degrees three, two, two and one. What is the sum of the degrees?

    Answer: ______________

  2. Which structure is a simple graph?

    • A multigraph with parallel edges between vertices
    • A directed graph with arrows on every edge
    • Vertices with at most one unoriented edge per pair and no loops
    • A hypergraph whose edges join triples of vertices

  3. Which structure is a simple graph?

    • Parallel edges plus loops allowed
    • One plain edge per pair at most, no loops
    • Every edge carries an arrow

  4. The sum of all vertex degrees of any finite graph is even.

    Circle one:   True   False

  5. A graph has degree sum thirty. How many edges does it have?

    Answer: ______________

  6. Which list can be the degrees of a simple graph on four vertices?

    • 2, 2, 2, 2
    • 4, 1, 1, 0
    • 3, 3, 3, 1

  7. A graph has seven edges. What is the sum of its vertex degrees?

    • 14
    • 7
    • 21
    • 9

  8. Two drawings with different edge crossings must represent different graphs. True or false?

    Circle one:   True   False

  9. A simple graph on five vertices has every vertex of degree 2. How many edges does it have?

    Answer: ______________

  10. Two drawings look different. What decides whether they show the same graph?

    • Whether the drawings look identical on paper
    • Whether vertex labels can be matched so adjacency is preserved
    • Whether they contain the same number of crossings
    • Whether they use the same colours for vertices
LightMySky · lightmysky.comW1-mt_1oqO_o3bTO-s1

Answer key

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

Graphs and the handshake lemma W1-mt_1oqO_o3bTO-s1

  1. 8 · Three plus two plus two plus one equals eight.
  2. Vertices with at most one unoriented edge per pair and no loops · Simple means one unoriented edge per pair at most, with no loops.
  3. One plain edge per pair at most, no loops · Simple means no loops and no doubled edges.
  4. True · The sum equals twice the edge count.
  5. 15 · Half of thirty is fifteen.
  6. 2, 2, 2, 2 · The four cycle realises all twos; 4 exceeds the maximum 3, and three 3s would force the fourth to 3.
  7. 14 · Twice seven is fourteen.
  8. False · False. Crossings depend on the drawing, not the graph.
  9. 5 · Degree sum ten halved gives five, realised by the five cycle.
  10. Whether vertex labels can be matched so adjacency is preserved · Graph identity is adjacency up to relabelling. Looks and crossings are irrelevant.
Worksheet · LightMySky