What Is A Euler Circuit

\(\def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #ane} \newcommand{\due south}[i]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.v,.6) node[above]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[in a higher place]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-ane) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.five,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-two,-i.5) rectangle (two,1.five)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (ii,1.five)} \def\E{\mathbb Eastward} \def\O{\mathbb O} \def\U{\mathcal U} \def\prisoner of war{\mathcal P} \def\inv{^{-i}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\saturday{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[ii]{node[make full,circle,inner sep=0pt, minimum size=4pt,label=#one:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[ane]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\five}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-ane.5,.6) node[in a higher place]{$A$}} \def\circleB{(.five,0) circle (1)} \def\circleBlabel{(ane.5,.6) node[above]{$B$}} \def\circleC{(0,-1) circumvolve (one)} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\twosetbox{(-2,-1.four) rectangle (two,i.iv)} \def\threesetbox{(-2.5,-ii.4) rectangle (two.5,1.4)} \def\ansfilename{do-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge x pct}}} \newcommand{\hexbox}[3]{ \def\10{-cos{30}*\r*#1+cos{30}*#2*\r*ii} \def\y{-\r*#one-sin{xxx}*\r*#1} \describe (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-ninety:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \depict (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \correct|} \newcommand{\twoline}[2]{\begin{pmatrix}#one \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Investigate! 35

An Euler path, in a graph or multigraph, is a walk through the graph which uses every edge exactly once. An Euler excursion is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

Which of the graphs below have Euler paths? Which have Euler circuits?
List the degrees of each vertex of the graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?
Is it possible for a graph with a degree 1 vertex to take an Euler excursion? If so, draw one. If non, explain why not. What about an Euler path?
What if every vertex of the graph has caste two. Is there an Euler path? An Euler circuit? Describe some graphs.
Below is part of a graph. Even though y'all tin only see some of the vertices, can yous deduce whether the graph will have an Euler path or circuit?

If we start at a vertex and trace along edges to go to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is next to the vertices earlier and afterward it in the sequence. If the walk travels forth every edge exactly once, and so the walk is called an Euler path (or Euler walk). If, in addition, the starting and ending vertices are the aforementioned (so you trace along every edge exactly once and end upward where y'all started), and then the walk is chosen an Euler circuit (or Euler tour). Of course if a graph is non connected, there is no hope of finding such a path or circuit. For the residuum of this section, assume all the graphs discussed are connected.

The bridges of Königsberg problem is actually a question near the existence of Euler paths. At that place will be a road that crosses every bridge exactly once if and only if the graph beneath has an Euler path:

This graph is small-scale enough that nosotros could really check every possible walk that does non reuse edges, and in doing so convince ourselves that there is no Euler path (permit alone an Euler excursion). On modest graphs which practice have an Euler path, it is usually not difficult to find one. Our goal is to find a quick fashion to check whether a graph has an Euler path or excursion, even if the graph is quite big.

One way to guarantee that a graph does not accept an Euler circuit is to include a "fasten," a vertex of degree 1.

The vertex $a$ has degree 1, and if you endeavor to make an Euler circuit, you see that you will become stuck at the vertex. Information technology is a dead cease. That is, unless y'all start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex $a\text{,}$ so loops effectually the triangle. You will end at the vertex of degree 3.

You run into a similar problem whenever y'all have a vertex of any odd degree. If you kickoff at such a vertex, you volition not be able to stop there (subsequently traversing every border exactly once). Afterward using one border to exit the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other one-half for leaving. And then you return, then leave. Return, then leave. The merely mode to employ up all the edges is to utilise the last one by leaving the vertex. On the other mitt, if you accept a vertex with odd degree that you do not start a path at, and then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to make it and leave again. Somewhen all but ane of these edges will be used up, leaving only an edge to go far by, and none to get out again.

What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at 1 of the odd degree vertices and end at the other. In such a situation, every other vertex must have an even caste since nosotros need an equal number of edges to get to those vertices as to leave them. How could nosotros have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to first there or end there, but not both. Thus for a graph to have an Euler excursion, all vertices must accept even degree.

The antipodal is also true: if all the vertices of a graph have even caste, and then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path. To testify this is a little tricky, just the basic idea is that y'all will never get stuck because there is an "outbound" edge for every "inbound" edge at every vertex. If you try to make an Euler path and miss some edges, yous will always exist able to "splice in" a circuit using the edges yous previously missed.

Euler Paths and Circuits

A graph has an Euler excursion if and but if the degree of every vertex is fifty-fifty.
A graph has an Euler path if and simply if at that place are at most 2 vertices with odd degree.

Since the bridges of Königsberg graph has all 4 vertices with odd degree, at that place is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

Subsection Hamilton Paths

Suppose you wanted to bout Königsberg in such a style where you visit each land mass (the two islands and both banks) exactly one time. This can be washed. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path). Nosotros could also consider Hamilton cycles, which are Hamliton paths which commencement and stop at the same vertex.

Example 4.4.one

Make up one's mind whether the graphs below have a Hamilton path.

Solution

The graph on the left has a Hamilton path (many different ones, actually), every bit shown here:

The graph on the right does not have a Hamilton path. You would need to visit each of the "outside" vertices, but as presently every bit you visit one, you get stuck. Note that this graph does non have an Euler path, although there are graphs with Euler paths simply no Hamilton paths.

Information technology appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. Nonetheless, nobody knows whether this is true. At that place is no known unproblematic test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an case of a question which as far every bit nosotros know is as well difficult for computers to solve; it is an case of a problem which is NP-complete.

Subsection Exercises

1

You and your friends want to tour the southwest by car. Y'all will visit the nine states beneath, with the following rather odd rule: you must cross each border between neighboring states exactly one time (so, for example, you must cross the Colorado-Utah border exactly one time). Can you do it? If so, does it matter where you start your route trip? What fact almost graph theory solves this trouble?

Solution

This is a question near finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly ii vertices volition have odd degree: the vertices for Nevada and Utah. Thus y'all must start your road trip at in one of those states and cease it in the other.

ii

Which of the following graphs contain an Euler path? Which contain an Euler circuit?

$K_4$
$K_5\text{.}$
$K_{5,7}$
$K_{2,7}$
$C_7$
$P_7$

Solution

$K_4$ does non accept an Euler path or circuit.
$K_5$ has an Euler excursion (so as well an Euler path).
$K_{five,seven}$ does not have an Euler path or circuit.
$K_{2,vii}$ has an Euler path merely not an Euler circuit.
$C_7$ has an Euler circuit (it is a circuit graph!)
$P_7$ has an Euler path but no Euler circuit.

3

Edward A. Mouse has just finished his brand new house. The floor program is shown below:

Edward wants to give a bout of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If and then, in which rooms must they begin and end the tour? Explain.
Is it possible to tour the house visiting each room exactly in one case (not necessarily using every doorway)? Explain.
Later a few mouse-years, Edward decides to remodel. He would like to add some new doors betwixt the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to accept an odd number of doors? Explain.

4

For which $n$ does the graph $K_n$ contain an Euler circuit? Explicate.

Solution

When $northward$ is odd, $K_n$ contains an Euler excursion. This is because every vertex has degree $n-i\text{,}$ then an odd $north$ results in all degrees beingness fifty-fifty.

5

For which $m$ and $n$ does the graph $K_{m,due north}$ incorporate an Euler path? An Euler excursion? Explain.

Solution

If both $thou$ and $north$ are even, then $K_{m,n}$ has an Euler excursion. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then in that location is an Euler path simply not an Euler circuit.

vi

For which $due north$ does $K_n$ contain a Hamilton path? A Hamilton cycle? Explain.

Solution

All values of $n\text{.}$ In particular, $K_n$ contains $C_n$ as a subgroup, which is a cycle that includes every vertex.

seven

For which $m$ and $n$ does the graph $K_{m,north}$ incorporate a Hamilton path? A Hamilton cycle? Explicate.

Solution

As long as $|m-n| \le i\text{,}$ the graph $K_{yard,n}$ will have a Hamilton path. To accept a Hamilton bicycle, we must have $m=n\text{.}$

8

A bridge builder has come to Königsberg and would similar to add bridges so that information technology is possible to travel over every bridge exactly once. How many bridges must be built?

Solution

If we build one bridge, we can have an Euler path. 2 bridges must exist built for an Euler excursion.

ix

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a fashion that every pupil sits between two friends? What does this question accept to do with paths?

Solution

We are looking for a Hamiltonian bike, and this graph does have ane:

ten

Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can accept? Explicate why your respond is correct.
Find a graph which does non have a Hamilton path even though no vertex has degree one. Explicate why your example works.

11

Consider the following graph:

Find a Hamilton path. Tin can your path be extended to a Hamilton bicycle?
Is the graph bipartite? If then, how many vertices are in each "office"?
Use your reply to role (b) to prove that the graph has no Hamilton cycle.
Suppose yous accept a bipartite graph $G$ in which one part has at to the lowest degree ii more than vertices than the other. Testify that $One thousand$ does not accept a Hamilton path.