Lesson test: Planarity and colouring

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Planarity and colouring

1.[1p]
A connected plane graph has $12$ vertices and $20$ edges. How many faces does it have, counting the outer face?

CorrectNot quite: 10

2.[1p]
What is the largest number of edges a simple planar graph with $10$ vertices can have?

CorrectNot quite: 24

3.[2p]
What is the largest number of edges a simple planar graph with $10$ vertices and no triangles can have?

CorrectNot quite: 16

4.[2p]
A convex polyhedron has $6$ square faces and $8$ triangular faces. How many vertices does it have?

CorrectNot quite: 12

5.[3p]
A connected plane graph has every vertex of degree $4$ and every face a triangle. How many vertices does it have?

CorrectNot quite: 6

6.[2p]
A graph consists of a cycle on $8$ vertices together with one more vertex joined to all eight. What is its chromatic number?

CorrectNot quite: 3

7.[1p]
Which of these graphs is planar?

$K_{5}$

The answer is: $K_{2,5}$

$K_{3, 3}$

The answer is: $K_{2,5}$

$K_{2, 5}$

Correct

The Petersen graph

The answer is: $K_{2,5}$

8.[3p]
Which of these statements are true?

Select all that apply

A graph with no cycle of odd length can be properly coloured with two colours

Correct

Every simple planar graph has a vertex of degree at most $5$

Correct

Every simple graph with $V \geq 3$ and $E \leq 3 V - 6$ is planar

The answer is: A graph with no cycle of odd length can be properly coloured with two colours, Every simple planar graph has a vertex of degree at most $5$

Kempe's 1879 argument proves that four colours suffice for every planar graph

The answer is: A graph with no cycle of odd length can be properly coloured with two colours, Every simple planar graph has a vertex of degree at most $5$

A graph with chromatic number $4$ must contain $K_{4}$

The answer is: A graph with no cycle of odd length can be properly coloured with two colours, Every simple planar graph has a vertex of degree at most $5$

Euler's formula $V - E + F = 2$ holds for every plane graph, connected or not

The answer is: A graph with no cycle of odd length can be properly coloured with two colours, Every simple planar graph has a vertex of degree at most $5$

9.[2p]
Put these events in chronological order, earliest first.

Kuratowski characterises the planar graphs
Appel and Haken prove the four colour theorem by computer
Heawood finds the flaw in Kempe's proof
Francis Guthrie asks whether four colours suffice for every map
Euler writes to Goldbach about $V - E + F = 2$
Gonthier checks the four colour theorem in Coq
Kempe publishes a proof of the four colour theorem

Show the answer

a, b, c, d, e, f, g

1.[1p] A connected plane graph has 12 vertices and 20 edges. How many faces does it have, counting the outer face?

2.[1p] What is the largest number of edges a simple planar graph with 10 vertices can have?

3.[2p] What is the largest number of edges a simple planar graph with 10 vertices and no triangles can have?

4.[2p] A convex polyhedron has 6 square faces and 8 triangular faces. How many vertices does it have?

5.[3p] A connected plane graph has every vertex of degree 4 and every face a triangle. How many vertices does it have?

6.[2p] A graph consists of a cycle on 8 vertices together with one more vertex joined to all eight. What is its chromatic number?

7.[1p] Which of these graphs is planar?

8.[3p] Which of these statements are true?

9.[2p] Put these events in chronological order, earliest first.

1.[1p]
A connected plane graph has $12$ vertices and $20$ edges. How many faces does it have, counting the outer face?

2.[1p]
What is the largest number of edges a simple planar graph with $10$ vertices can have?

3.[2p]
What is the largest number of edges a simple planar graph with $10$ vertices and no triangles can have?

4.[2p]
A convex polyhedron has $6$ square faces and $8$ triangular faces. How many vertices does it have?

5.[3p]
A connected plane graph has every vertex of degree $4$ and every face a triangle. How many vertices does it have?

6.[2p]
A graph consists of a cycle on $8$ vertices together with one more vertex joined to all eight. What is its chromatic number?

7.[1p]
Which of these graphs is planar?

8.[3p]
Which of these statements are true?

9.[2p]
Put these events in chronological order, earliest first.