Eulerizing a Graph | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Eulerizing a Graph

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.8 · lesson 66 of 878 min · free with a free account

← Euler's Theorems: Degrees, Paths, and CircuitsNext lesson: Hamiltonian Paths and Circuits →

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

When no Euler circuit exists: repeat as little as possible.

  • Eulerize a graph by duplicating edges
  • Explain why duplicating a path fixes 2 parities
  • Solve a small Chinese Postman Problem
  • Know where exact solutions stop being practical

Transcript

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

Graph Theory: Foundations and Euler Paths

Eulerizing a Graph

This section closes chapter nine by asking what to do when no Euler circuit exists. The technique is called eulerizing a graph. It repeats some edges, as few and as cheaply as possible, until an Euler circuit appears. Choosing the cheapest repetition is a famous optimization problem, the Chinese postman problem.

The Opening Problem

Sweep Every Street, Return to the Depot

A public works department must sweep every street in a small neighborhood at least once this week, and the sweeper truck must return to its depot. The street map is a connected graph. But a few intersections have an odd number of streets meeting there. So by the last three sections, no route covers every street exactly once and returns home. The department can't delete streets, and it won't build new ones. Its only option is to let the truck drive down some existing streets twice. So which streets should be driven twice? How few extra blocks does that take? And why does it matter, for a truck burning fuel every mile?

Definition 9.8.1

Eulerization

An eulerization of a connected graph with some odd vertices duplicates existing edges, adding no new vertices and no new streets, until every vertex has even degree. Then theorem nine point seven point three guarantees an Euler circuit. Here's why duplicating works. Suppose you duplicate every edge along a path between two odd vertices, u and v. Each vertex in the middle of the path gains exactly two, one duplicate arriving and one leaving. So an even degree stays even. The two endpoints each gain exactly one. And odd plus one is even. So duplicating a path between two odd vertices fixes both of their parities, and disturbs no other. Pair up all the odd vertices that way, duplicate a path for each pair, and every degree becomes even.

Worked Example

A 3-by-3 Street Grid

Here's the department's neighborhood. Nine intersections in a three-by-three grid. Every block is one unit long, except two longer ones. B two to C two is three blocks, and C one to C two is two blocks. All together, the streets total fifteen blocks. Four intersections, A two, B one, B three, and C two, have degree three. They're shown in red. Every other intersection has even degree. The thick edges show the cheapest set of duplications, which we're about to find.

A Valid, Not Optimal, Eulerization

Pair A2 With C2, B1 With B3

First, one valid eulerization, though not yet the cheapest. Pair A two with C two, and B one with B three. Duplicate the path A two, B two, C two. That's one plus three, four blocks. And duplicate B one, B two, B three, two blocks. Now every degree is even. B two, which sits on both paths, gains four, going from four to eight. So there's an Euler circuit. The truck could follow it. But it would drive six extra blocks. Is there a cheaper pairing?

Definition 9.8.2

The Chinese Postman Problem

Given a connected graph with weighted edges, the Chinese postman problem asks for the minimum total weight closed walk, one that covers every edge at least once. Equivalently, it asks for the cheapest eulerization. It's also called the route inspection problem. It's named for the Chinese mathematician Mei-Ko Kwan, also written Guan Meigu, who posed it in nineteen sixty, in a paper on optimizing postal delivery routes. For an undirected graph, it can be solved efficiently. Pair up the odd vertices using a minimum weight perfect matching, where the cost of pairing two vertices is the shortest path distance between them. Then duplicate the edges along each chosen shortest path. Jack Edmonds's work on matching is what makes that efficient.

Table 9.8.1

3 Ways to Pair 4 Odd Vertices

For the grid, there are exactly three ways to split the four odd vertices into two pairs. Pairing A two with B one, and B three with C two, costs two plus two, which is four. Pairing A two with B three, and B one with C two, costs two plus three, which is five. And pairing A two with C two, and B one with B three, costs four plus two, which is six. That's the one we tried first. So the optimal pairing adds only four blocks. And notice that it never touches the long block from B two to C two. The postman routes around the expensive street, instead of duplicating it. The shortest possible sweeping route is fifteen plus four, nineteen blocks.

Listing 1

Checking Every Pairing

A short program checks every pairing. The shortest path distances between the odd vertices go into a table. A recursive function then generates every way to split the list into pairs. It pairs the first vertex with each possible partner, and recurses on what's left. The cost of a pairing is the sum of its distances. Taking the minimum gives A two with B one, and B three with C two, at a cost of four. The source computes those distances with a graph library. Here they're taken straight from the table.

Why Brute Force Stops Working

Pairings Explode

For larger networks, checking every pairing stops being practical. With two k odd vertices, the number of pairings is two k minus one, times two k minus three, and so on, down to one. Four odd vertices give just three pairings, manageable by hand. But a real neighborhood with twenty odd intersections gives six hundred fifty-four million, seven hundred twenty-nine thousand, and seventy-five pairings. Far too many to list. That's why real routing software relies on a polynomial time matching algorithm, not brute force.

9.8.3 and 9.8.4

Where the Postman Problem Shows Up

The name comes from mail delivery, but the same structure appears everywhere. Street sweeping and snow plowing, trash collection, meter reading, and inspection runs along power lines or pipelines. In each case, the edges are segments that must be visited, not just reached, and the weights are real distances or drive times. There's a catch. Real streets include one-way segments. The problem is solvable in polynomial time when the graph is entirely undirected, or entirely directed. But on a mixed graph, with both one-way and two-way streets, it's N P complete, as Christos Papadimitriou proved. And most real city grids are mixed. So route planning software for such networks relies on heuristics, like those for the traveling salesman problem, covered later with Hamiltonian circuits. A fast, good route beats an exact answer that might never finish computing.

Takeaways

Repeat Wisely

To summarize. Eulerizing a graph means duplicating existing edges, never adding new ones, until every degree is even. Duplicating a full path between two odd vertices fixes both endpoints, and leaves every interior vertex's parity alone. Eulerization is never unique. And the Chinese postman problem finds the cheapest one, by a minimum weight matching of the odd vertices, using shortest path distances. Undirected and fully directed networks have efficient exact solutions. Mixed networks make the problem N P complete. Here's something to think about. A student duplicates the edge from A two to B two, and says the department now needs to build a new road. Is that right? What does a duplicated edge actually represent about the truck's route? And a second student asks why only paths between odd vertices get duplicated. What would go wrong, and to which vertices' parity, if a path between two even vertices were duplicated instead?

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 Eulerizing a Graph

What does it mean to eulerize a graph?
Eulerizing a connected graph means duplicating some existing edges until every vertex has even degree, so an Euler circuit exists. It adds no new vertices and no new streets. A duplicated edge just means the route travels that edge a second time. The goal is to duplicate as few edges, or as little total weight, as possible.
Why does duplicating a path between two odd vertices make both of them even?
Duplicating every edge along a path between odd vertices u and v adds 1 to the degree of each endpoint, and odd plus 1 is even. Each vertex in the middle of the path gains exactly 2, one duplicate edge arriving and one leaving, so its parity does not change. Pairing all odd vertices this way makes every degree even.
How do you solve a small Chinese postman problem, like a street grid with four odd vertices?
List every way to pair the odd vertices, add the shortest-path distance for each pair, and choose the cheapest pairing. In the 3-by-3 grid with odd vertices A2, B1, B3, and C2, the pairings cost 2+2=4, 2+3=5, and 4+2=6. The cheapest adds 4 blocks, so the shortest route is 15+4=19 blocks.
When does solving the Chinese postman problem by checking every pairing stop being practical?
Checking every pairing stops being practical on larger networks because the count explodes. With 2k odd vertices there are (2k-1)(2k-3)\cdots 1 pairings. Four odd vertices give 3, but twenty give 654,729,075. Undirected graphs are instead solved efficiently with a minimum weight perfect matching. Mixed graphs with one-way and two-way streets are NP-complete, so software uses heuristics.

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 →