Euler's Theorems: Degrees, Paths, and Circuits | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 9.7 Free with a free account

Euler's Theorems: Degrees, Paths, and Circuits

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.7 · lesson 65 of 8710 min · free with a free account

← Fleury's AlgorithmNext lesson: Eulerizing a Graph →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Why counting odd degrees settles the question - proved in both directions.

  • Prove the Handshaking Theorem and its corollary
  • Prove an Euler circuit forces even degrees
  • Prove even degrees guarantee an Euler circuit
  • Extend the proof to Euler paths

Transcript

Everything said in the video, section by section (1,546 words). Read along, or search it.

Graph Theory: Foundations and Euler Paths

Euler's Theorems: Degrees, Paths, and Circuits

Section nine point five stated the degree conditions for Euler paths and circuits, and section nine point six built the walks. This section proves the conditions, in both directions, with no step skipped. It starts from the handshaking theorem, then proves necessity, then sufficiency, and finally extends everything to Euler paths.

The Opening Problem

Is the Walk Even Possible?

A regional data center operator maintains a metropolitan fiber network linking five central hubs. Before sending a technician to inspect every fiber run in one continuous walk, a costly procedure, operations wants a fast yes or no. Is such a walk even possible, without doubling back over any run? The remarkable fact, first analyzed by Leonhard Euler in seventeen thirty-six, is that the answer depends on a single count at each hub. How many fiber runs meet there. This section proves exactly why that count settles the question. One note. The graphs here may have parallel edges, but no loops. Every argument counts edge endpoints at a vertex, so it works for multigraphs too.

Theorem 9.7.1

The Handshaking Theorem

The first result holds for every graph, with no conditions at all. The degrees add up to twice the number of edges. The proof counts edge endpoints in two ways. Vertex by vertex, the total is the degree sum. Edge by edge, each edge has exactly two endpoints, so it contributes exactly two to the total, whichever vertices it joins. That's twice the number of edges. Both methods count the same endpoints, so the totals agree. A corollary follows. The number of odd-degree vertices is always even. Split the degree sum into even-degree and odd-degree vertices. The even ones give an even sum, and the total is even, so the odd ones give an even sum too. Write each odd degree as two m plus one. Their sum is twice the sum of the m's, plus k, the number of odd vertices. That's even only when k is even.

Figure 9.7.1

A Dual-Ring Network

Here's the operator's network, on the left. Two redundant fiber rings, A B C and C D E, share a single core hub, C. A, B, D, and E each have degree two, and C has degree four. There are six fiber runs. The degrees add to twelve, which is twice six, just as the theorem says. Every vertex has even degree. So the number of odd vertices is zero, which is even, as the corollary requires. On the right is the same network with one run, from E to C, not yet installed. We'll come back to that version at the end.

Theorem 9.7.2 - Necessity

An Euler Circuit Forces Even Degrees

Now the Euler circuit criterion, which needs two separate proofs. First, necessity. If a graph has an Euler circuit, every vertex has even degree. Write the circuit as a sequence, v zero, e one, v one, and so on, back to v zero. Every edge appears exactly once. Fix any vertex w, and look at every place it appears. If w appears in the middle, the walk arrives on one edge and leaves on the next. Those are two distinct edges, since the circuit repeats none. So that visit accounts for a matched pair of endpoints at w. If w is the shared start and end, the first edge leaves it and the last edge returns to it. Again two distinct edges, a matched pair. Every edge at w appears somewhere in the circuit, and every appearance contributes endpoints in pairs. So the degree of w is even. And w was arbitrary.

Worked Example

Pairs, Hub by Hub

Here's that pairing argument, made concrete. Trace the circuit A, B, C, D, E, C, and back to A on the dual-ring network. A leaves on the first edge, and returns on the last. That's one pair, a total of two. B, D, and E each arrive on one edge and leave on the next. Each has a total of two. And C is visited twice in the middle. Each visit gives a full pair, arriving and leaving, so C's total is four. Every total is even, built entirely from matched pairs, exactly as the proof describes.

Theorem 9.7.3 - Sufficiency

Even Degrees Guarantee a Circuit

The converse is harder. If a graph is connected, and every vertex has even degree, then it has an Euler circuit. The proof uses one fact. If every vertex has degree at least two, the graph contains a cycle. Here's why. Start anywhere and keep leaving each vertex on an edge you haven't just used. Degree at least two means that's always possible. And since the graph is finite, you must eventually revisit a vertex, which closes a cycle. The proof itself is by strong induction on the number of edges, m. The base case is m equals zero. A connected graph with no edges is a single vertex. The empty closed walk there is, vacuously, an Euler circuit.

The Inductive Step

Remove a Cycle, Recurse, Splice

For the inductive step, take a connected graph with even degrees and m edges, at least one. Every vertex then has degree at least two, so the graph contains a cycle, Z. Remove the edges of Z. Each vertex on the cycle loses exactly two, so its parity is preserved. Every other degree is unchanged. So what remains still has all even degrees, with fewer edges. What remains may fall into several pieces. But each piece with edges is connected, all even, and smaller, so by induction, it has its own Euler circuit. And every such piece shares a vertex with Z. Otherwise, nothing could connect that piece to the rest of the graph, and the graph is connected. So build the circuit. Walk around Z. Each time you reach a vertex shared with an unvisited piece, detour through that piece's whole circuit, then resume Z. Every edge of Z, and every edge of every piece, is used exactly once, and the walk returns to its start. That's an Euler circuit.

Worked Example

Splicing the 2 Rings

Apply that construction to the dual-ring network. Take Z to be the first ring, A, B, C. Removing it leaves the second ring, C, D, E, one piece, which shares the vertex C with Z. A triangle is its own Euler circuit, C, D, E, back to C. Now splice. Start at C, detour through the whole second ring, C, D, E, C, then walk the first ring, C, A, B, C. That uses all six edges, each exactly once, and returns to C. It's just a rotation of the circuit traced a moment ago.

Theorem 9.7.4

Euler Paths: Exactly 2 Odd Vertices

Networks aren't always this symmetric. The last theorem extends everything to open paths. A connected graph has an Euler path exactly when zero, or exactly two, vertices have odd degree. With two, every Euler path runs from one of them to the other. Zero is the circuit case, already proved. For necessity with an open path, every vertex other than the ends pairs up its visits, as before, so its degree is even. But the starting vertex has one extra departure, with no arrival to match it. So its degree is odd. The same goes for the ending vertex, reading backward. So exactly those two are odd. For sufficiency, add one auxiliary edge between the two odd vertices, just for the proof. Now every degree is even, and the graph is still connected, so it has an Euler circuit. Rotate that circuit so the auxiliary edge comes last, then delete it. What's left uses every original edge exactly once, running from one odd vertex to the other.

Worked Example

The Incomplete Network

Now the incomplete network, where the run from E to C hasn't been installed. The edges are A B, B C, C A, C D, and D E. C now has degree three and E has degree one. Exactly two odd vertices. Follow the proof. Add the auxiliary edge E C. That rebuilds the dual-ring network, with its circuit. Rotate it to end with E C. C, A, B, C, D, E, then back to C. Delete that last edge, and the trail C, A, B, C, D, E remains. It covers exactly the five runs that actually exist. So a technician can inspect this network in one continuous walk, but only by starting or ending at C or E.

Table 9.7.1

The 2 Criteria Compared

This table compares the two criteria. An Euler circuit needs exactly zero odd vertices. It closes up, and it can start anywhere. An open Euler path needs exactly two odd vertices, and runs from one to the other. With four or more odd vertices, neither exists. And counts of one, three, or five are impossible, by the corollary. Both criteria also need every edge in a single connected component.

Takeaways

Necessity, Sufficiency, and an Extra Edge

To summarize. The handshaking theorem holds for every graph, and its corollary says odd-degree vertices always come in an even number. Necessity and sufficiency are separate proofs. One shows the degree condition can't be avoided. The other shows it's enough, given connectivity, by removing a cycle, recursing, and splicing. And one auxiliary edge turns an Euler path question into an already solved circuit question. Here's something to think about. A facility has two pieces of cabling, never connected. A short run, X, Y, Z, and a separate triangle, U, V, W. Across the whole facility, exactly two vertices, X and Z, have odd degree. By the degree count alone, the path condition looks satisfied. Is there an Euler path using every cable exactly once? If not, which hypothesis fails? And why can checking parity never substitute for checking connectivity?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Euler's Theorems: Degrees, Paths, and Circuits

What does the Handshaking Theorem say, and why must the number of odd-degree vertices be even?
The Handshaking Theorem says the degrees of all vertices add up to twice the number of edges, \sum \deg(v) = 2|E|. Each edge has two endpoints, so it adds exactly 2 to the total. The sum is therefore even. Even-degree vertices contribute an even amount, so the odd-degree vertices must also sum to an even number, which forces their count to be even.
Why does a graph with an Euler circuit have to have every vertex of even degree?
Every vertex of a graph with an Euler circuit has even degree because the circuit pairs up the edges at each vertex. Each time the walk passes through a vertex, it arrives on one edge and leaves on a different one. The start vertex pairs its first and last edges. Every edge appears exactly once, so the degree is a sum of pairs.
How do you prove that a connected graph with all even degrees has an Euler circuit?
Use strong induction on the number of edges m. With m=0, the graph is a single vertex, and the empty closed walk works. Otherwise, all degrees are at least 2, so a cycle Z exists. Removing Z keeps every degree even. Each remaining piece with edges has an Euler circuit by induction, and each touches Z. Splice those circuits into Z at shared vertices.
How do you show a connected graph with exactly two odd vertices has an Euler path?
Add one auxiliary edge joining the two odd-degree vertices. Every degree is now even, and the graph is still connected, so it has an Euler circuit. Rotate that circuit so the new edge comes last, then delete it. The remaining walk uses every original edge exactly once and runs from one odd vertex to the other.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →