0

Eulerian and Hamiltonian Graphs

Description: Eulerian and Hamiltonian Graphs Quiz
Number of Questions: 15
Created by:
Tags: graph theory eulerian graph hamiltonian graph
Attempted 0/15 Correct 0 Score 0

In a connected graph, an Eulerian path is a path that:

  1. Visits every vertex exactly once

  2. Visits every edge exactly once

  3. Visits every vertex at least once

  4. Visits every edge at least once


Correct Option: B
Explanation:

An Eulerian path is a path that visits every edge of a graph exactly once. It is not necessary for the path to visit every vertex of the graph.

In a connected graph, an Eulerian circuit is a circuit that:

  1. Visits every vertex exactly once

  2. Visits every edge exactly once

  3. Visits every vertex at least once

  4. Visits every edge at least once


Correct Option: A
Explanation:

An Eulerian circuit is a circuit that visits every vertex of a graph exactly once. It is not necessary for the circuit to visit every edge of the graph.

Which of the following graphs has an Eulerian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: C
Explanation:

A cycle is a graph that consists of a single circuit. Since every vertex in a cycle has degree 2, it is possible to find an Eulerian circuit in a cycle.

Which of the following graphs has an Eulerian path but not an Eulerian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: D
Explanation:

A path is a graph that consists of a single path. Since the endpoints of a path have degree 1, it is not possible to find an Eulerian circuit in a path. However, it is possible to find an Eulerian path in a path by starting at one endpoint and ending at the other endpoint.

Which of the following graphs does not have an Eulerian path or an Eulerian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: B
Explanation:

A tree is a graph that is connected and has no cycles. Since every vertex in a tree has degree 1 or 2, it is not possible to find an Eulerian path or an Eulerian circuit in a tree.

In a connected graph, a Hamiltonian path is a path that:

  1. Visits every vertex exactly once

  2. Visits every edge exactly once

  3. Visits every vertex at least once

  4. Visits every edge at least once


Correct Option: A
Explanation:

A Hamiltonian path is a path that visits every vertex of a graph exactly once. It is not necessary for the path to visit every edge of the graph.

In a connected graph, a Hamiltonian circuit is a circuit that:

  1. Visits every vertex exactly once

  2. Visits every edge exactly once

  3. Visits every vertex at least once

  4. Visits every edge at least once


Correct Option: A
Explanation:

A Hamiltonian circuit is a circuit that visits every vertex of a graph exactly once. It is not necessary for the circuit to visit every edge of the graph.

Which of the following graphs has a Hamiltonian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: A
Explanation:

A complete graph is a graph in which every vertex is connected to every other vertex. Since every vertex in a complete graph has degree n-1, where n is the number of vertices in the graph, it is possible to find a Hamiltonian circuit in a complete graph.

Which of the following graphs has a Hamiltonian path but not a Hamiltonian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: D
Explanation:

A path is a graph that consists of a single path. Since the endpoints of a path have degree 1, it is not possible to find a Hamiltonian circuit in a path. However, it is possible to find a Hamiltonian path in a path by starting at one endpoint and ending at the other endpoint.

Which of the following graphs does not have a Hamiltonian path or a Hamiltonian circuit?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: B
Explanation:

A tree is a graph that is connected and has no cycles. Since every vertex in a tree has degree 1 or 2, it is not possible to find a Hamiltonian path or a Hamiltonian circuit in a tree.

Euler's formula states that for a connected graph with v vertices and e edges, the following equation holds:

  1. v + e = 2

  2. v - e = 2

  3. v + e = f

  4. v - e = f


Correct Option: C
Explanation:

Euler's formula states that for a connected graph with v vertices and e edges, the following equation holds: v + e = f, where f is the number of faces in the graph.

Which of the following graphs has an odd number of vertices?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: D
Explanation:

A path is a graph that consists of a single path. Since the endpoints of a path have degree 1, the number of vertices in a path is always odd.

Which of the following graphs has an even number of vertices?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: A
Explanation:

A complete graph is a graph in which every vertex is connected to every other vertex. Since every vertex in a complete graph has degree n-1, where n is the number of vertices in the graph, the number of vertices in a complete graph is always even.

Which of the following graphs has an odd number of edges?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: C
Explanation:

A cycle is a graph that consists of a single circuit. Since every edge in a cycle is incident to two vertices, the number of edges in a cycle is always even.

Which of the following graphs has an even number of edges?

  1. A complete graph

  2. A tree

  3. A cycle

  4. A path


Correct Option: A
Explanation:

A complete graph is a graph in which every vertex is connected to every other vertex. Since every vertex in a complete graph has degree n-1, where n is the number of vertices in the graph, the number of edges in a complete graph is always n(n-1)/2, which is even.

- Hide questions