Top Topics

Wednesday, February 5, 2014

Euler Paths and Circuits

My son brought home a packet about Euler Paths and Circuits.  My brain was a little rusty in this area and he wasn't that familiar with the Euler concepts, so I did a little research and made him a "study sheet" to help him out (okay, I'll admit that it will also help me out if I have to teach this concept when subbing at school).  I thought I'd share my sheet with you.  Please let me know if you have feedback on how to improve it.





I really do find these interesting - they are like puzzles in a way.  It is amazing that some people's brains can see the paths very easily and others (like me) have to work a little harder.  I think people with good spatial skills (or who are gifted in the "non-verbal" area) tend to solve these quite quickly.  Good thing that my kids took after their dad in this area. ;)

Here are a few links to help explain Euler Circuits and Paths - 
An Introduction to Euler Circuits and Paths
The Seven Bridges of Konigsberg (extension idea - try eliminating a bridge to see if you can make a Euler Path or Circuit)



There are lots of ways to apply Euler Circuits and Paths in real life.  This website looked at the game Ticket to Ride to examine if there were any Euler Circuits and Paths (spoiler alert - there are none).



Leonhard Euler lived from 1707 to 1783 and was a Swiss mathematician (one of the greatest of all time). Euler spend a lot of his career working at the Berlin Academy in Germany.  He became famous when he was given "The Seven Bridge of Konigsberg" question to solve.

Here's some information from my study sheet: 


EULER’S THEOREMS
Euler’s Theorem 1 - If a graph has any vertices of odd degree, then it CANNOT have an EULER CIRCUIT AND If a graph is connected and every vertex has even degree, then it has AT LEAST ONE EULER CIRCUIT (usually more).
Euler’s Theorem 2 - If a graph has more than 2 vertices of odd degree, then it CANNOT have an EULER PATH AND If a graph is connected and has exactly 2 vertices of odd degree, then it has AT LEAST ONE EULER PATH (usually more). Any such path must start at one of the odd-degree vertices and end at the other.
Euler’s Theorem 3 - The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).  In every graph, the number of vertices of odd degree must be even.
Keep in mind:
*An Euler Circuit IS a type of Euler Path but an Euler Path is not necessarily an Euler Circuit.
*The sum of the degrees of all the vertices of a graph is twice the number of edges.
*The number of vertices of odd degree must be even.

Connected Graph:
-A vertex-edge graph is connected if there is a path between all pairs of vertices.
-If a path does NOT exist between all pairs of vertices, then the graph is disconnected.
-The # of edges that meet at a vertex in a vertex-edge graph
- If there are an even # of edges that meet at a vertex, then the degree of the vertex is even.
-If there are an odd # of edges that meet at a vertex, then the degree of the vertex is odd.


Degree of a Vertex:
-The # of edges that meet at a vertex in a vertex-edge graph
- If there are an even # of edges that meet at a vertex, then the degree of the vertex is even.
-If there are an odd # of edges that meet at a vertex, then the degree of the vertex is odd.

My double bubble map (yes, I know I am nerdy to do this at home but it is how I think)...

Here's a simple chart to remember if something is an Euler Path or an Euler Circuit...


1 comment:

Anonymous said...

As a high school math teacher who is currently teaching this unit, I would say you did a great job on your "cheat sheet." :-)