Edge walks are easy, vertex tours are hard

Mathematics · Discrete Mathematics · ages 21-22

Name ______________________ Date ____________

A connected graph has vertex degrees 3, 3, 2, 2, 2, 2. How many edges does it have? Give a number.
Answer: ______________
A connected graph has vertex degrees 2, 2, 4, 4, 2, 2. What must it contain?
- An Euler circuit
- An Euler trail but no circuit
- No Euler trail at all
- A Hamilton cycle
A connected graph has vertex degrees 2, 2, 4, 4, 2, 2. What must it contain?
- An Euler circuit
- An Euler trail but no circuit
- No Euler trail at all
A connected graph has vertex degrees 3, 3, 2, 2, 2, 2. How many edges does it have?
Answer: ______________
A connected graph has vertex degrees 3, 3, 2, 2, 4, 4. What must it contain?
- An Euler trail but no Euler circuit
- An Euler circuit
- No Euler trail at all
- Two separate Euler circuits
Eli says Euler trails have a quick degree check but Hamilton cycles have no such quick test. Is Eli right?
Circle one: True False
A connected graph holds an Euler trail. What must its odd count look like?
- At least four odd vertices in every trail
- Zero or two odd vertices, running odd to odd when two
- No even degree vertices anywhere
Eli says Euler trails have a quick degree check but Hamilton cycles have no such quick test. Is Eli right?
Circle one: True False
A graph breaks the minimum degree rule for Hamilton cycles yet still holds one. What does this show?
- That the condition is false
- That Euler trails are hard to check
- That the condition is not necessary
A graph breaks the minimum degree rule for Hamilton cycles yet still contains one. What does this example show about the rule?
- That the condition is not necessary
- That the condition is false
- That the graph has no Hamilton cycle
- That Euler trails are hard

Answer key

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

Edge walks are easy, vertex tours are hard W1-mt_RU5P5Iqekt-s1

7 · Degrees sum to 14, and the edge count is half the degree sum: 14 divided by 2 = 7.
An Euler circuit · Every vertex has even degree, so the graph has an Euler circuit: a closed walk using each edge once.
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.
An Euler trail but no Euler circuit · Exactly two vertices have odd degree, which is the signature of a trail that must start at one odd vertex and end at the other.
True · Parity decides Euler trails quickly, while no such fast test is known for Hamilton cycles.
Zero or two odd vertices, running odd to odd when two · Trails need zero odds for a closed walk, or two odds joined by the route.
True · Eli is right. Parity of degrees decides Euler trails quickly, while no such fast test is known for Hamilton cycles, which are hard to decide.
That the condition is not necessary · A one way promise can stay true while cycles appear below its bar.
That the condition is not necessary · A sufficient condition guarantees a cycle when it holds but says nothing when it fails, so a cycle here only shows it is not necessary.