Back To Course

Math 106: Contemporary Math9 chapters | 106 lessons

Are you a student or a teacher?

Try Study.com, risk-free

As a member, you'll also get unlimited access to over 75,000 lessons in math, English, science, history, and more. Plus, get practice tests, quizzes, and personalized coaching to help you succeed.

Try it risk-freeWhat teachers are saying about Study.com

Already registered? Login here for access

Your next lesson will play in
10 seconds

Lesson Transcript

Instructor:
*Yuanxin (Amy) Yang Alcocer*

Amy has a master's degree in secondary education and has taught math at a public charter high school.

Watch this video lesson, and you will see how you can turn a math problem into a challenging brain game. Learn what it means for a graph to be Eulerian or semi-Eulerian.

I remember being challenged to a brain game where I am given a picture of a graph with dots and connecting lines and told to figure out a way to draw the same figure without lifting my pencil and only drawing each side once. I was not allowed to go over a side I had already drawn. Little did I know then that what I was doing was actually related to the topic we are discussing in this video lesson.

What I did was I drew an **Euler path**, a path in a graph where each side is traversed exactly once. A graph with an Euler path in it is called **semi-Eulerian**. I thoroughly enjoyed the challenge and thought little of the math connections it had. Let me show you the brain game I was given.

To draw this shape without lifting my pencil and going over each line exactly once, I had to begin at the point 1, then go to point 3, then 2, then 4, and then 3 again. Do you see how we went over each line just once? That is the defining characteristic of an Euler graph. Also, note that we ended up in a different spot.

Another characteristic of a semi-Eulerian graph is that at most two of the vertices will be of odd degree, meaning they will have an odd number of edges connecting it to other vertices. All the other vertices will be even. In this graph, we see that vertices 1 and 3 are odd, while 2 and 4 are even.

Let's look at another example. This time, see if you can figure it out.

Again, what we are trying to do is to find a path in the graph so that we are crossing every edge exactly once. Remember that a path takes you from one point to a different point. Can you find one in this graph?

Try starting at point 2. Now go down to point 1. Then point 4, back to point 2, point 3, and then finally point 4. We have an Euler path! We have crossed each edge exactly once. So this means that this graph is semi-Eulerian.

Are there other Euler paths in this graph? Yes, there are. We can also note these Euler paths by just writing the names of the vertices that we pass. So, another Euler path in this graph is 4, 3, 2, 4, 1, 2. Notice that with all these paths, we end up at a different point than where we began. Are there more ways to draw this shape using an Euler path? I won't tell you what they are, but I will tell you there are a total of 6 Euler paths in this graph. What makes each path different is the order in which the edges are drawn.

If we end up at the same point that we started, then we have what is called an **Euler circuit**, a circuit in a graph where each edge is traversed exactly once and that starts and ends at the same point. Look at this graph and see if you can draw it without lifting your pencil, going over each edge only once, and starting and ending at the same point:

Just like with Euler paths, we can have multiple Euler circuits in a graph. This is a simple example, and you might already see a number of ways to draw this shape using an Euler circuit. Because this graph has an Euler circuit in it, we call this graph **Eulerian**. One Euler circuit that this graph has is 2, 3, 4, 1, 2. Alternately, you can also draw this shape by following the Euler circuit 1, 2, 3, 4, 1. Note that our start and end points are the same in these circuits. We end up where we began.

Also, for a Eulerian graph, all the vertices are even, meaning that all the vertices will have an even number of edges connecting it to others. Look at our graph above, and you will see that all of our vertices have an even number of edges.

We can have simple Euler circuits, and we can also have more complex Euler circuits. Let's look at one. See if you can spot the Euler circuit yourself this time.

This time, the edges are labeled instead of the vertices. Can you draw this one using an Euler circuit? Follow the edges in alphabetical order, and you will see an Euler circuit. This means that this graph is Eulerian. Do you see more Euler circuits in this graph? I see at least one more.

Let's review what we've learned. An **Euler path** is a path in a graph where each side is traversed exactly once. A graph with an Euler path in it is called **semi-Eulerian**. At most, two of these vertices in a semi-Eulerian graph will be odd. All others will be even. An **Euler circuit** is a circuit in a graph where each edge is traversed exactly once and that starts and ends at the same point. A graph with an Euler circuit in it is called **Eulerian**. All the vertices in an Eulerian graph will be even. You can have multiple Euler paths in a graph. You can also have multiple Euler circuits in a graph. The difference between each path and circuit is the order in which edges are passed.

After this lesson, you'll have the ability to:

- Define Euler path and Euler circuit
- Explain what semi-Eulerian and Eulerian graphs are

To unlock this lesson you must be a Study.com Member.

Create your account

Are you a student or a teacher?

Already a member? Log In

BackWhat teachers are saying about Study.com

Already registered? Login here for access

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

You are viewing lesson
Lesson
3 in chapter 9 of the course:

Back To Course

Math 106: Contemporary Math9 chapters | 106 lessons

- Introduction to Graph Theory 4:34
- Graph Theory Concepts and Terminology 8:08
- Euler Paths and Euler's Circuits 6:11
- Euler's Theorems: Circuit, Path & Sum of Degrees 4:44
- Fleury's Algorithm for Finding an Euler Circuit 5:20
- Eulerizing Graphs in Math 5:57
- Hamilton Circuits and Hamilton Paths 3:26
- Assessing Weighted & Complete Graphs for Hamilton Circuits 5:06
- The Traveling Salesman Problem in Computation 4:46
- Methods of Finding the Most Efficient Circuit 8:17
- Go to Graph Theory

- Electricity, Physics & Engineering Lesson Plans
- Teaching Economics Lesson Plans
- U.S. Politics & Civics Lesson Plans
- US History - Civil War: Lesson Plans & Resources
- Computer Science 321: Ethical Hacking
- iOS Data Analysis & Recovery
- Acquiring Data from iOS Devices
- Foundations of Digital Forensics
- Introduction to Mobile Forensics
- Examination of iOS Devices
- CNE Prep Product Comparison
- IAAP CAP Prep Product Comparison
- TACHS Prep Product Comparison
- Top 50 Blended Learning High Schools
- EPPP Prep Product Comparison
- NMTA Prep Product Comparison
- Study.com NMTA Scholarship: Application Form & Information

- History of Sparta
- Realistic vs Optimistic Thinking
- How Language Reflects Culture & Affects Meaning
- Logical Thinking & Reasoning Questions: Lesson for Kids
- Amigo Brothers Activities
- Using Graphical Objects in Python
- Tundra Biome Project Ideas
- Quiz & Worksheet - Frontalis Muscle
- Octopus Diet: Quiz & Worksheet for Kids
- Quiz & Worksheet - Fezziwig in A Christmas Carol
- Quiz & Worksheet - Dolphin Mating & Reproduction
- Flashcards - Measurement & Experimental Design
- Flashcards - Stars & Celestial Bodies
- ESL Conversation Questions & Topics for ESL Students
- Social Emotional Learning SEL Resources for Teachers

- American Literature: Certificate Program
- Introduction to Environmental Science: Help and Review
- NJBCT: Study Guide & Practice
- GACE Middle Grades Social Science (015): Practice & Study Guide
- AEPA Reading Endorsement 6-12 (AZ047): Practice & Study Guide
- CEOE Early Childhood Ed: Basic Math & Problem Solving
- Ohio Graduation Test: Reading Comprehension
- Quiz & Worksheet - After Twenty Years Themes & Analysis
- Quiz & Worksheet - Characteristics of Baroque Architecture
- Quiz & Worksheet - Evoked Set in Marketing
- Quiz & Worksheet - Calculating Mark Up
- Quiz & Worksheet - Theory & Proof of Abiogenesis

- Sticky Prices: Definition, Theory & Model
- The Veldt by Ray Bradbury: Summary & Setting
- How to Choose a Dissertation Topic
- Pennsylvania Homeschool Laws
- Homeschooling in Oregon
- Earth Science Projects
- Logical Reasoning Questions on the LSAT
- AP World History Exam Scores
- 504 Plans in Georgia
- What Are the SAT Test Registration Deadlines?
- The New SAT Math Section
- Homeschooling in Connecticut

- Tech and Engineering - Videos
- Tech and Engineering - Quizzes
- Tech and Engineering - Questions & Answers

Browse by subject