به انگلیسی

Color maps and test flat drawings

Mathematics · Discrete Mathematics · ages 21-22

Name ______________________ Date ____________

A connected plane graph has 9 edges and 5 faces, including the outer face. How many vertices does it have?
Answer: ______________
The complete simple graph on four vertices has maximum degree 3. What is its chromatic number?
- 4
- 3
- 2
- 1
A simple graph has vertices A, B, C, D and exactly the edges AB, BC, CD, DA. What is the minimum number of colours needed for a proper vertex colouring?
- 2
- 3
- 4
A connected plane graph has 8 vertices and 12 edges. How many faces does its drawing have, including the outer face?
Answer: ______________
A graph with a loop can have a proper vertex colouring if enough colours are available. True or false?
Circle one: True False
A connected simple graph has 7 vertices and 14 edges. Since 14 <= 3 × 7 - 6, this inequality alone proves that the graph is planar. True or false?
Circle one: True False
Which argument proves Euler's formula for every finite connected plane graph by deleting cycle edges until a tree remains? Count the outer face.
- Each deletion preserves V - E + F; the final tree has E = V and F = 1, so the original expression is 1.
- Each deletion preserves V - E + F; the final tree has E = V - 1 and F = 0, so the original expression is 1.
- Each deletion preserves V - E + F; the tree has E = V - 1 and F = 1, so the original expression is 2.
- The final tree has E = V - 1 and F = 1; deletions reduce V - E + F, so its original value exceeds 2.
In greedy colouring of a finite simple graph with maximum degree Δ, why does a palette of Δ + 1 colours always leave a colour for the next vertex?
- Every earlier vertex must have its own separate colour
- Every later neighbour has already received its own colour
- At most Δ colours are blocked by coloured neighbours
The complete simple graph on five vertices has 10 edges. Which edge-count argument proves that it is not planar?
- Its 10 edges fall below the simple planar limit for five vertices
- Its 10 edges exceed the simple planar limit of 9
- Its five vertices require exactly four colours in every drawing
A connected simple plane graph has 8 vertices. Every face boundary, including the outer one, has length 3. How many edges does it have?
Answer: ______________

Answer key

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

Color maps and test flat drawings W1-mt_6xy6UPBppw-s1

6 · Euler's formula gives V = 2 + E - F = 2 + 9 - 5 = 6.
4 · Every pair is adjacent, so all four vertices need different colours. Four colours suffice and attain the maximum-degree-plus-one bound.
2 · An edge requires two different colours. Alternating two colours around this four-cycle works, so the minimum is 2.
6 · Euler's formula gives F = 2 - V + E = 2 - 8 + 12 = 6. The outer face is included.
False · A loop joins a vertex to itself. Proper colouring would require its colour to differ from itself, which no palette can achieve.
False · The cap is 15, so 14 passes the edge-count test. Passing a necessary condition does not prove that a crossing-free drawing exists.
Each deletion preserves V - E + F; the tree has E = V - 1 and F = 1, so the original expression is 2. · Cycle-edge deletion preserves connectivity and V - E + F. The final tree has E = V - 1 and F = 1, giving V - (V - 1) + 1 = 2. Since each deletion preserves the expression, its value was also 2 in the original drawing.
At most Δ colours are blocked by coloured neighbours · Only already coloured neighbours restrict the current vertex. There are at most Δ of them, so they block at most Δ of the Δ + 1 available colours.
Its 10 edges exceed the simple planar limit of 9 · A connected simple planar graph with five vertices has at most 3 × 5 - 6 = 9 edges. Ten edges exceed that limit.
18 · The boundary count gives 3F = 2E. Euler gives F = E - 6. Hence 3E - 18 = 2E, so E = 18.