Euler Paths and Circuits Basics Quiz

1) An Euler path in a graph is a path that:

Visits every vertex exactly once

Uses every edge at least once

Uses every edge exactly once

Uses every vertex and edge exactly once

An Euler path uses each edge exactly once.

Explanation

An Euler path uses each edge exactly once.

2) An Euler circuit (or Euler cycle) is:

An Euler path that starts and ends at the same vertex

Any cycle in the graph

A path that visits each vertex once

A walk with no repeated vertices

An Euler circuit is a closed Euler path.

Explanation

An Euler circuit is a closed Euler path.

3) Every Euler circuit is also an Euler path.

True

False

A circuit is a special closed Euler path.

Explanation

A circuit is a special closed Euler path.

4) A connected graph has an Euler circuit if and only if:

Exactly two vertices have odd degree

All vertices have even degree

All vertices have odd degree

It is a tree

Euler circuit ⇔ every vertex has even degree.

Explanation

Euler circuit ⇔ every vertex has even degree.

5) A connected graph has an Euler path but not an Euler circuit if and only if:

All vertices have even degree

Exactly one vertex has odd degree

Exactly two vertices have odd degree

At least three vertices have odd degree

Euler path (not circuit) ⇔ exactly two vertices have odd degree.

Explanation

Euler path (not circuit) ⇔ exactly two vertices have odd degree.

6) If a connected graph has three vertices of odd degree, it cannot have an Euler path.

True

False

Odd-degree vertices must be 0 or 2 for an Euler path.

Explanation

Odd-degree vertices must be 0 or 2 for an Euler path.

7) In a connected graph, if there are no vertices of odd degree, then:

No Euler path exists

An Euler circuit exists

Exactly one Euler path exists

The graph must be a tree

All degrees even ⇒ Euler circuit exists.

Explanation

All degrees even ⇒ Euler circuit exists.

8) Which classical puzzle is modeled by an Euler path problem?

Traveling salesman problem

Königsberg bridges problem

Shortest path in a grid

Coloring of a map

Königsberg bridges problem deals with using each bridge once.

Explanation

Königsberg bridges problem deals with using each bridge once.

9) A connected graph has vertex degrees 2,3,3,2. What can we say about Euler paths?

It has no Euler path

It has an Euler circuit

It has an Euler path but not an Euler circuit

It must be a tree

Two odd-degree vertices ⇒ Euler path, no circuit.

Explanation

Two odd-degree vertices ⇒ Euler path, no circuit.

10) To check for an Euler path, it is enough to look at the degrees of vertices and connectivity of the graph.

True

False

Euler path criteria depend on degrees and connectivity.

Explanation

Euler path criteria depend on degrees and connectivity.

11) Which of the following must be true for any graph with an Euler circuit?

It has at least one vertex of odd degree

The sum of degrees is odd

Every vertex has even degree

It is complete

Euler circuits require all degrees even.

Explanation

Euler circuits require all degrees even.

12) A graph has 6 vertices; 4 have degree 2 and 2 have degree 4. What can we say?

It has no Euler path

It has an Euler path but not an Euler circuit

It has an Euler circuit

It cannot be connected

All degrees even ⇒ Euler circuit exists.

Explanation

All degrees even ⇒ Euler circuit exists.

13) Consider a path graph (P4) with 4 vertices in a line. Does it have an Euler path?

Yes, and also an Euler circuit

Yes, but no Euler circuit

No Euler path

Only if we add a loop

P4 has exactly two odd vertices ⇒ Euler path but no circuit.

Explanation

P4 has exactly two odd vertices ⇒ Euler path but no circuit.

14) A cycle graph Cn (n ≥ 3) always has an Euler circuit.

True

False

All vertices have degree 2 ⇒ Eulerian.

Explanation

All vertices have degree 2 ⇒ Eulerian.

15) In an undirected graph, each edge contributes how much to the total sum of degrees?

0

1

2

Depends on the graph

Each edge contributes 2 (one per endpoint).

Explanation

Each edge contributes 2 (one per endpoint).