图论问题：是否存在含Eulerian Trail与Hamiltonian Cycle但无Eulerian circuit的图？

Absolutely! This is totally possible, and constructing such a graph is straightforward once you nail down the core rules for each of these graph structures. Let’s break it down:

Key Background Recap #

First, let’s refresh the critical conditions we need to hit:

• Eulerian Circuit: A connected graph where every vertex has an even degree. If this is true, you can traverse every edge exactly once and end back at your starting vertex.
• Eulerian Trail: A connected graph where exactly 0 or 2 vertices have odd degrees. The 0-odd-degree case is actually just an Eulerian circuit, so we need the 2-odd-degree version to avoid having an Eulerian circuit.
• Hamiltonian Cycle: A cycle that visits every vertex in the graph exactly once (and returns to the start). It doesn’t care about edge counts, just full vertex coverage.

A Simple Example Graph #

Let’s build a tiny, easy-to-visualize graph that fits all our requirements:

• Vertices: {1, 2, 3, 4}
• Edges: {(1,2), (2,3), (3,4), (4,1), (1,3)}

In plain terms, this is a 4-sided cycle (a square) with a diagonal edge connecting vertex 1 to vertex 3.

Verifying All Conditions #

Let’s check each requirement one by one:

1. No Eulerian Circuit:

   • Vertex 1 has degree 3 (connected to 2, 4, and 3)
   • Vertex 3 has degree 3 (connected to 2, 4, and 1)
   • Vertices 2 and 4 have degree 2 each.
     Since we have two vertices with odd degrees, we can’t have an Eulerian circuit (which requires all even degrees).

2. Has an Eulerian Trail:

   • The graph is fully connected, and we have exactly two vertices with odd degrees (1 and 3). This fits the exact condition for an Eulerian Trail. One such trail would be: 1 → 2 → 3 → 4 → 1 → 3 (traverses every edge exactly once, starts at 1 and ends at 3).

3. Has a Hamiltonian Cycle:

   • The original 4-cycle works perfectly here: 1 → 2 → 3 → 4 → 1. This cycle visits every vertex exactly once and returns to the starting point, which matches the definition of a Hamiltonian Cycle.

Bonus: Another Quick Example #

If you want something slightly different, take a 5-vertex cycle (which has a Hamiltonian cycle by default) and add an edge between two adjacent vertices. This will make those two vertices have odd degrees (each goes from degree 2 to 3), giving you an Eulerian trail but no Eulerian circuit—while keeping the original 5-cycle as a valid Hamiltonian cycle.

内容的提问来源于stack exchange，提问作者user535785