Practice: Graphs · The Lumenary

Graphs

Warm-upHuman

A graph has seven vertices, with degrees $3, 3, 2, 2, 2, 1, 1$ . How many edges does it have?

Graphs

Warm-upHuman

Can there be a group of $7$ people in which every person knows exactly $3$ of the others (knowing being mutual)?

Choose one

No: the numbers of acquaintances would add up to

7 \times 3 = 21

, which is odd, but they must add up to twice the number of pairs who know each other.Yes: arrange the

7

people in a circle and let each know their neighbours and the person opposite.No, because

3

is more than half of

7

.Yes, but only if one person knows nobody.

Graphs

CoreHuman

An engineering cooperative lays water pipes to connect $50$ villages in a region of Bolivia so that water can flow between any two villages, using as few pipes as possible: the network has no loops. Each pipe joins two villages. How many pipes are there?

Graphs

CoreHuman

A connected graph has six vertices with degrees $2, 4, 3, 3, 4, 2$ . Which statement is true?

Choose one

It has an Euler trail that starts at one vertex of degree

3

and ends at the other, but no Euler circuit.It has an Euler circuit.It has no Euler trail at all.Such a graph cannot exist, because the degrees add up to an odd number.

Graphs

CoreHuman

The cube graph has the $8$ corners of a cube as vertices and its $12$ edges as edges. Which statements are true? (Choose all that apply.)

Choose all that apply

It has a Hamiltonian cycle (a cycle visiting every vertex exactly once).It has an Euler circuit.It has no Euler trail.It has

\frac{8 \times 3}{2} = 12

edges, consistent with the handshake lemma.

Graphs

CoreHuman

To prove that a tree with at least two vertices has a leaf, we take a longest path $v_0, v_1, \dots, v_k$ and show that $v_k$ is a leaf. Why can $v_k$ have no neighbour other than $v_{k-1}$ ?

Choose one

A neighbour outside the path would give a longer path, and a neighbour

v_i

with

i < k - 1

would close a cycle.Because a tree with

n

vertices has

n - 1

edges.Because the degrees add up to twice the number of edges.Because

v_k

was chosen to have the smallest degree.

Graphs

StretchHuman

How many trees with $5$ vertices are there up to isomorphism — that is, how many different shapes?

Graphs

StretchFormal

In the lesson's Lean model, IsEulerCircuit G w says that the walk w crosses every edge of the multigraph G exactly once and ends where it started. Which statement is a correct formalisation of the necessity half of Euler's theorem for circuits?

Choose one

IsEulerCircuit G w → ∀ v, Even (degree G v)(∀ v, Even (degree G v)) → ∃ w, IsEulerCircuit G wIsEulerCircuit G w → ∃ v, Even (degree G v)IsEulerCircuit G w → ∀ v, Odd (degree G v)

Graphs

StretchComputational

A connected multigraph on the vertices $0, 1, \dots, n - 1$ is given as a list of edges (a, b) (pairs may repeat). Write euler_status(n, edges) that returns "circuit" if it has an Euler circuit, "trail" if it has an Euler trail but no circuit, and "none" otherwise, using Euler's theorem. (Assume at least one edge.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.