Section 1.2 - Finding Euler Circuits
Instructions
- The first video below explains the concepts in this section.
- This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.
Concepts
- Degree (or valence) of vertices in a graph
- Euler's Theorem on when a graph has an Euler path or Euler circuit
- Simple graphs and graphs with loops
- Connected and disconnected graphs
Exercises
Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.
1. Find the valence of each vertex and show that \(d=2e.\)
\(A=3\), \(B=5\), \(C=3\), \(D=3\)
\(d=14\), \(e=7\) \(\Rightarrow d=2e\)
\(d=14\), \(e=7\) \(\Rightarrow d=2e\)
2. Is this graph connected? If not, how many components are there?
No, 2 components
3. Use Euler's Theorem to determine if there is an Euler circuit, an Euler path, or neither.
neither
4. Use Euler's Theorem to determine if there is an Euler circuit, an Euler path, or neither.
Euler circuit
5. Use Euler's Theorem to determine if there is an Euler circuit, an Euler path, or neither.
neither
6. Use Euler's Theorem to determine if there is an Euler circuit, an Euler path, or neither.
Euler path
7. Verify that the following graph has an Euler circuit. Then, find 3 different circuits.
connected and even-valent \(\Rightarrow\) Euler circuit
ABDCBEDFEA, AEFDEBCDBA, BDCBEDFEAB, AEBCDEFDBA, etc.
ABDCBEDFEA, AEFDEBCDBA, BDCBEDFEAB, AEBCDEFDBA, etc.