In-Depth Eulerian Graph Theory and Trail Analysis Quiz

1) Which best describes an Euler walk in a finite undirected graph?

A walk that visits every vertex exactly once

A closed walk containing all vertices

A walk that uses every edge exactly once

A walk of maximum possible length

By definition, an Euler walk (Euler trail) traverses each edge exactly once.

Explanation

By definition, an Euler walk (Euler trail) traverses each edge exactly once.

2) Ignoring isolated vertices, a graph must be connected in order to admit an Euler trail.

True

False

All edges must be reachable in a single continuous traversal.

Explanation

All edges must be reachable in a single continuous traversal.

3) For an undirected graph, which numbers of vertices of odd degree are compatible with having an Euler trail?

Only 0

Only 2

0 or 2

Any even number

Euler trail ⇔ number of odd-degree vertices is 0 (circuit) or 2 (open trail).

Explanation

Euler trail ⇔ number of odd-degree vertices is 0 (circuit) or 2 (open trail).

4) Consider a connected graph whose vertex degrees are {1,2,2,3}. What can we conclude?

It has an Euler circuit

It has an Euler trail but not an Euler circuit

It has no Euler trail

It cannot exist

Exactly two vertices are odd → Euler trail but no Euler circuit.

Explanation

Exactly two vertices are odd → Euler trail but no Euler circuit.

5) Which degree multiset must correspond to a connected graph with an Euler circuit?

{2,2,2,2}

{1,1,2,2}

{1,3,3,3}

{1,1,1,1}

All degrees are even → necessary for an Euler circuit.

Explanation

All degrees are even → necessary for an Euler circuit.

6) For the star graph (K_{1,k}), for which (k) does it admit an Euler trail?

(k = 1) only

(k = 2) only

All even (k)

All odd (k)

Degree pattern gives exactly two odd vertices only when (k = 2).

Explanation

Degree pattern gives exactly two odd vertices only when (k = 2).

7) In any finite undirected graph, the sum of all vertex degrees is an even number.

True

False

Each edge contributes 2 to the sum of degrees.

Explanation

Each edge contributes 2 to the sum of degrees.

8) A connected graph has 8 vertices and exactly two of them have odd degree. What can be said about Euler walks?

It has no Euler walk

It has an Euler circuit

It has an Euler trail but not an Euler circuit

It must be a tree

Exactly two odd vertices → Euler trail but no circuit.

Explanation

Exactly two odd vertices → Euler trail but no circuit.

9) In a directed graph, which statement is necessary for a directed Euler circuit to exist?

Every vertex has in-degree zero

Every vertex has the same in-degree and out-degree

Every vertex has even out-degree

There is a Hamiltonian cycle

Directed Euler circuits require balanced in-degree and out-degree.

Explanation

Directed Euler circuits require balanced in-degree and out-degree.

10) In a directed graph, the sum of all in-degrees equals the sum of all out-degrees.

True

False

Each directed edge contributes exactly 1 to each sum.

Explanation

Each directed edge contributes exactly 1 to each sum.

11) A connected graph has degrees {2,2,4,4,4}. What can we say about Euler walks?

No Euler trail exists

There is an Euler trail but not an Euler circuit

There is an Euler circuit

It cannot be connected

All degrees are even → Euler circuit exists.

Explanation

All degrees are even → Euler circuit exists.

12) Which scenario is naturally modelled by finding an Euler trail in a street network graph?

Visiting each intersection exactly once

Driving each road segment exactly once

Minimizing total travel time between two fixed points

Avoiding any repeated vertices

To traverse each road segment exactly once corresponds to an Euler trail.

Explanation

To traverse each road segment exactly once corresponds to an Euler trail.

13) If a connected undirected graph has an Euler circuit, removing any single edge necessarily destroys all Euler circuits.

True

False

Some edges can be removed while preserving all-even degrees and connectivity.

Explanation

Some edges can be removed while preserving all-even degrees and connectivity.

14) In a directed multigraph, which pair of conditions is sufficient to guarantee a directed Euler circuit?

Strong connectivity and in-degree(v) = out-degree(v) for all v

Weak connectivity and all in-degrees even

Strong connectivity and all out-degrees equal

A Hamiltonian cycle and at least one loop

Directed Eulerian criterion: balanced in/out-degree + strong connectivity.

Explanation

Directed Eulerian criterion: balanced in/out-degree + strong connectivity.

15) A connected undirected graph has exactly four vertices of odd degree. Minimum edges to add?

1

2

3

4

One edge fixes two odd vertices → 4 odd needs 2 edges.

Explanation

One edge fixes two odd vertices → 4 odd needs 2 edges.