Essential Quiz: Eulerian and Hamiltonian Paths and Circuits Quiz

Explore the fundamentals of Eulerian and Hamiltonian paths and circuits with targeted questions designed to reinforce concepts like graph traversal, cycles, and connectivity. Test your understanding of definitions, necessary conditions, and distinct properties within graph theory relevant to Eulerian and Hamiltonian concepts.

1. Definition of Eulerian Circuit

   Which of the following best defines an Eulerian circuit in a connected graph?

   1. A cycle that visits each vertex and edge exactly once.
   2. A cycle that traverses each edge exactly once and returns to the starting vertex.
   3. A path that visits every vertex exactly once without repeating any edge.
   4. A sequence that visits every vertex at least once and repeats edges if needed.

   Explanation: An Eulerian circuit is a closed path that uses every edge of the graph exactly once, ending at the starting vertex. Option two incorrectly focuses on vertices, not edges. The third option adds a requirement (visiting each vertex exactly once) that is not needed for Eulerian circuits. Option four allows repeated edges, which is not allowed in Eulerian circuits.

2. Condition for Eulerian Path Existence

   A connected undirected graph has exactly two vertices of odd degree. Which statement is true about Eulerian paths?

   1. The graph has both an Eulerian path and an Eulerian circuit.
   2. The graph has an Eulerian path but not an Eulerian circuit.
   3. The graph must have a Hamiltonian circuit.
   4. The graph has neither an Eulerian path nor an Eulerian circuit.

   Explanation: A connected graph with exactly two vertices of odd degree will have an Eulerian path but won't have an Eulerian circuit. The first option is correct because Eulerian circuits require all vertices to have even degree. The second option is incorrect because a circuit cannot exist with odd degree vertices. The third misses that a path still exists. The fourth option confuses Eulerian properties with Hamiltonian circuits.

3. Hamiltonian Path Characteristic

   What is a defining feature of a Hamiltonian path in a graph?

   1. It covers each edge exactly once.
   2. It visits every vertex exactly once.
   3. It forms a complete graph with all possible edges.
   4. It connects all vertices to a central vertex.

   Explanation: A Hamiltonian path passes through every vertex of a graph once without repetition. It is not required to use each edge, making option two incorrect, as that's a property of Eulerian paths. Option three mistakenly describes a star graph property. Option four inaccurately refers to a complete graph, which is unrelated to Hamiltonian paths.

4. Necessary Condition for Eulerian Circuit

   For a connected undirected graph to contain an Eulerian circuit, what must be true about the degrees of its vertices?

   1. Exactly two vertices must have odd degree.
   2. All vertices must have degree at least three.
   3. Every vertex must have an even degree.
   4. All vertices must have degree one.

   Explanation: An Eulerian circuit requires all vertices to have even degree, ensuring that you can enter and leave every vertex an equal number of times. The second option allows only a path, not a circuit, if two vertices have odd degree. Having all degrees one or at least three doesn't guarantee Eulerian circuits, making options three and four incorrect.

5. Difference Between Eulerian and Hamiltonian Paths

   How does a Hamiltonian path differ from an Eulerian path?

   1. A Hamiltonian path starts and ends at the same vertex; an Eulerian path does not.
   2. An Eulerian path visits every vertex exactly once; a Hamiltonian path repeats vertices.
   3. A Hamiltonian path visits every vertex once; an Eulerian path traverses every edge once.
   4. Only Eulerian paths can exist in disconnected graphs.

   Explanation: The distinction is that Hamiltonian paths focus on visiting every vertex exactly once, while Eulerian paths are about traversing every edge once. Option two violates the definition, as Hamiltonian paths don't require returning to the start. Option three incorrectly switches properties. Option four is wrong since Eulerian paths require the graph to be connected.

6. Simple Graph and Eulerian Circuit

   Consider a simple connected graph with four vertices, each having degree 2. Which statement is true?

   1. The graph must have a Hamiltonian circuit.
   2. The graph cannot have any circuits.
   3. The graph must be disconnected.
   4. The graph contains an Eulerian circuit.

   Explanation: If all vertices have even degree and the graph is connected, an Eulerian circuit exists. Although the graph may also have a Hamiltonian circuit, that's not guaranteed just by degrees alone, making the second option too strong. The third and fourth options are incorrect because the graph is connected and at least one circuit is possible.

7. Hamiltonian Circuit in Complete Graph

   Which complete graph with n vertices is guaranteed to have a Hamiltonian circuit?

   1. K5 (complete graph with 5 vertices)
   2. K2 (complete graph with 2 vertices)
   3. K3 (complete graph with 3 vertices)
   4. K1 (complete graph with 1 vertex)

   Explanation: A complete graph with n ≥ 3 has a Hamiltonian circuit, so K5 (five vertices) fits this. K2 only has one edge and can't form a circuit. K1 has too few vertices for a circuit. Although K3 (three vertices) does have a Hamiltonian circuit, the question asks which is guaranteed, and K5 is the most illustrative and typical for Hamiltonian circuits among the options.

8. Eulerian Circuit Example

   Given a figure-eight graph (two cycles sharing a single vertex), does it have an Eulerian circuit?

   1. Yes, because all vertices have even degree.
   2. Yes, but only if it is a bipartite graph.
   3. No, unless the cycles are of the same length.
   4. No, because it is not connected.

   Explanation: In a figure-eight graph, if each vertex has even degree, an Eulerian circuit exists. The connectivity is not an issue here, so the second option is incorrect. Bipartiteness is irrelevant for Eulerian circuits, negating the third option. Cycle lengths do not affect the existence of an Eulerian circuit if vertex degrees meet the condition, making the fourth incorrect.

9. Hamiltonian Path in a Tree

   Which statement about the existence of Hamiltonian paths in a tree with n vertices is correct?

   1. A Hamiltonian path exists only if the tree is a star.
   2. A tree has a Hamiltonian path only if all vertices have degree two.
   3. A Hamiltonian path cannot exist in a tree.
   4. Any tree with n vertices has at least one Hamiltonian path.

   Explanation: In any tree, visiting all vertices along a longest path (from one leaf to another) forms a Hamiltonian path. The second option is incorrect as stars are just one type of tree. The third option contradicts the definition. The fourth is false since degrees in a tree can vary and still allow a Hamiltonian path.

10. Checking for Eulerian Path

    Which property should you verify first to quickly determine if a connected undirected graph has an Eulerian path?

    1. Count the number of vertices of odd degree.
    2. Determine if all vertices have the same degree.
    3. Count the total number of edges.
    4. Check if it's a bipartite graph.

    Explanation: The key step is counting vertices with odd degree; a connected graph has an Eulerian path if there are exactly two or zero. Bipartiteness does not affect Eulerian paths, making option two irrelevant. The total number of edges not directly determines path existence. Equal degrees across vertices are not a requirement for Eulerian paths, so the last option is also incorrect.