به انگلیسی

Euler trails and Hamilton cycles

Mathematics · Discrete Mathematics · ages 21-22

Name ______________________ Date ____________

A graph has exactly the edges AB, BC, CA, CD, DE, EC. A proposed Euler circuit is A-B-C-A. How many graph edges does it omit?
Answer: ______________
A graph has exactly the edges AB, BC, CA, AD, DE, EA. Which route joins the closed trails A-B-C-A and A-D-E-A at A?
- A-B-C-A-B-C-A
- A-B-C-A-D-E-D-A
- A-B-C-D-E-A
- A-B-C-A-D-E-A
A connected graph has vertex degrees 2, 2, 4, 4, 2, 2. What must it contain?
- An Euler circuit
- An open Euler trail
- No Euler trail
A connected graph has vertex degrees 3, 3, 2, 2, 2, 2. How many edges does it have?
Answer: ______________
A connected undirected graph has degrees A: 3, B: 4, C: 2, D: 1, E: 2. Which vertices must be the endpoints of an open Euler trail?
- B and C, the vertices with even degrees
- A and B, the vertices with largest degrees
- A and D, the vertices with odd degrees
- C and E, the vertices with degree two
Eli says connectivity and degree parity decide Euler trail existence in O(V + E) time with adjacency lists, while no polynomial-time algorithm is known for Hamilton cycle existence on general simple undirected graphs. Is this correct?
Circle one: True False
A finite connected undirected graph has exactly two odd vertices u and v. Why does adding a temporary edge uv, allowing a parallel edge, prove that the original graph has an open Euler trail?
- Delete temporary uv at any position; the remaining list is always a trail
- Write temporary uv last in an Euler circuit; delete it to leave an open trail
- Keep temporary uv in the Euler circuit; the route then uses only original edges
A simple undirected graph with at least three vertices and a degree-1 vertex can have a Hamilton cycle. Is this statement true?
Circle one: True False
The cycle graph C6 has six vertices, all of degree 2. It has a Hamilton cycle but fails Dirac's degree bound. What does this show about Dirac's condition?
- The condition cannot guarantee any Hamilton cycle
- The condition is necessary for every Hamilton cycle
- The condition is sufficient, but not necessary
A simple undirected graph has 8 vertices. Every pair of distinct nonadjacent vertices has degree sum at least 8. What does Ore's theorem guarantee?
- An Euler circuit exists because every degree is even
- A Hamilton cycle exists by Ore's degree condition
- No Hamilton cycle exists because the graph is sparse
- Exactly two vertices in the graph have odd degree

Answer key

For grown-ups. Fold this page away before handing over the rest.

Euler trails and Hamilton cycles W1-mt_RU5P5Iqekt-s1

3 · The route uses AB, BC and CA. It omits CD, DE and EC, so it misses 3 edges and is not an Euler circuit.
A-B-C-A-D-E-A · Insert the second closed trail at A. A-B-C-A-D-E-A uses all six listed edges once and returns to A.
An Euler circuit · All six degrees are even, so zero odds gives a closed walk over each edge once.
7 · Degrees sum to 14, and each edge adds 2 to that sum, so 14 divided by 2 is 7.
A and D, the vertices with odd degrees · A has degree 3 and D has degree 1. They are the only odd-degree vertices, so an open Euler trail must run between them.
True · The Euler test checks connectivity and odd degrees in linear time. General Hamilton cycle existence is NP-complete; no polynomial-time algorithm is known.
Write temporary uv last in an Euler circuit; delete it to leave an open trail · Adding uv makes every degree even, so the augmented graph has an Euler circuit. Write the temporary edge last and delete it. The remaining route uses every original edge once between u and v.
False · Every vertex on a Hamilton cycle needs two distinct incident edges. A degree-1 vertex has only one, so no Hamilton cycle can include it.
The condition is sufficient, but not necessary · Dirac's bound is 6/2 = 3. C6 has degree 2 at every vertex yet has a Hamilton cycle, so the sufficient condition is not necessary.
A Hamilton cycle exists by Ore's degree condition · Ore requires degree sum at least n for every distinct nonadjacent pair. Here n = 8 and every required sum meets that bound, so a Hamilton cycle exists.