\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}
\begin{document}
\module{Eulerian graphs}{2}{19}{2 periods}
\en\nocouleur
%\prereq{}
\object{\begin{itemize}
\item Introduce the vocabulary about graphs.
\item Discover the main results about eulerian and traversable graphs.
\end{itemize}}
\mater{\begin{itemize}
\item Lesson (36 copies).
\item Problems (36 copies).
\end{itemize}}
\modpart{Appetizer : three eulerian problems}{Previous period}
Three famous problems (The bridges of Konigsberg and the house with 5 rooms, with or without a door to the outside) are
presented to the students. They have to solve them for the next period.
\modpart{The solutions}{10 mins}
The solutions to the three problems are given by the teacher or students.
\modpart{Quick lesson}{20 mins}
The vocabulary about graphs is introduced, and then the main results about eulerian graphs.
\modpart{Solving problems}{Remaining time}
Students are working in pairs. They have to solve 10 problems about eulerian graphs. Each problem is worth 2 points and
a mark is given to each pair at the end of the second period.
\pagebreak
\moddocdis{Eulerian graphs}{2}{19}{Lesson}
A graph $G$ is a set of point, the \emph{vertices}, along with a set of line segments or curves joining some of these
vertices, the \emph{edges}. The \emph{order} of a graph is its number of vertices while its \emph{size} is its number of
edges.
\section{Connected graphs}
Let $u$ and $v$ be two vertices in a graph $G$. As an example, we will consider the graph drawn below.
\begin{center}
\includegraphics[width=7cm]{s02e19/example1.eps}
\end{center}
The vertices $u$ and $v$ are said to be \emph{adjacent} if the edge $uv$ is part of the graph. In the same situation, we
say that the edge $uv$ is \emph{incident} to the vertices $u$ and $v$.
\bigskip
The \emph{degree} of a vertex is the number of edges adjacent to it. If the degree of a vertex is even, we simply say
that it's an \emph{even vertex}, and similarly for an \emph{odd vertex}.
\bigskip
\begin{itemize}
\itemb A $u-v$ \emph{walk} is a sequence of adjacent vertices beginning with $u$ and ending with $v$. In the example, a
$v_1-v_3$ walk is $v_1$, $v_2$, $v_3$, $v_7$, $v_2$, $v_3$, $v_4$, $v_3$.
\itemb A $u-v$ \emph{trail} is a $u-v$ walk which does not repeat any edge. In the example, a $v_1-v_3$ trail is $v_1$,
$v_2$, $v_7$, $v_3$, $v_4$, $v_3$.
\itemb A $u-v$ \emph{path} is a $u-v$ trail which does not repeat any vertex. In the example, a $v_1-v_3$ path is $v_1$,
$v_2$, $v_7$, $v_3$.
\end{itemize}
\bigskip
Two vertices $u$ and $v$ are \emph{connected} if either $u=v$ or there exists a $u-v$ path from $u$ to $v$. A graph is
\emph{connected} if every two vertices are connected. Otherwise, it is \emph{disconnected}. Our example is obviously a
connected graph.
\bigskip
\begin{itemize}
\itemb A $u-v$ trail which contains at least three vertices and such that $u=v$ is called a \emph{circuit}. In our
example, $v_2$, $v_7$, $v_3$, $v_6$, $v_5$, $v_4$, $v_3$, $v_2$ is a circuit.
\itemb A circuit which does not repeat any vertices is called a \emph{cycle}. In our example, $v_2$, $v_7$, $v_3$, $v_2$
is a cycle.
\end{itemize}
\pagebreak
\section{Eulerian graphs}
A circuit containing all edges of a graph $G$ is called an \emph{eulerian circuit}. A graph containing an eulerian
cicuit is called an \emph{eulerian graph}. It's easy to see that our example is not an eulerian graph, because of the
edge $v_1v_2$.
\bigskip
\theo{}{A graph is eulerian if and only if it is connected and every vertex is even.}
\bigskip
If a graph $G$ has a trail, not a circuit, containing all edges of $G$, $G$ is called a \emph{traversable} graph and the
trail is called an \emph{eulerian trail}.
We can see, by trial and error, that our example is not a traversable graph.
\bigskip
\theo{}{A graph is traversable if and only if it is connected and has exactly two odd vertices. Furthermore, any
eulerian
trail in such a graph begins at one of the odd vertices and ends at the other.}
\bigskip
\pagebreak
\moddocdis{Eulerian graphs}{2}{18}{Problems}
\newcounter{prob}
\newcommand{\prob}{\stepcounter{prob}\subsection*{Problem \arabic{prob}}}
\prob
Classify the following graphs as eulerian, traversable or neither. For the first two kinds, find an eulerian circuit or
trail.
\begin{center}
\includegraphics[width=13cm]{s02e19/euleriangraphs1.eps}
\end{center}
\prob
Suppose you hold a summer job as a highway inspector. Among your responsabilities, you must periodically drive along the
several highways shown schematically in the figure below and inspect the roads for debris and possible repairs. If you
live in town A, is it possible to find a round trip, beginning and ending at A, which takes you over each section of
highway exactly once ? If you were to move to town B, would it be possible to find such a round trip beginning and
ending at B ?
\begin{center}
\includegraphics[width=6cm,angle=90]{s02e19/euleriangraph2.eps}
\end{center}
\pagebreak
\prob
The figure below shows the blueprint of a house. Can a person walk through each doorway of this house once and only once
? If so, show how it can be done.
\begin{center}
\includegraphics[width=8cm]{s02e19/euleriangraph3.eps}
\end{center}
\prob
A letter carrier is responsible for delivering mail to houses on both sides of the streets shown in the figure below. If
the letter carrier does not keep crossing s street back and forth to get to houses on both sides of a street, it will be
necessary for her to walk along a street at least twice, once on each side, to deliver the mail. Is it possible for the
letter carrier to construct a round trip so that she walks on each side of every street exactly once ?
\begin{center}
\includegraphics[width=10cm]{s02e19/euleriangraph4.eps}
\end{center}
\pagebreak
\prob
Give an example of a graph or order 10 which is
\begin{enumerate}
\item eulerian ;
\item traversable ;
\item neither eulerian nor traversable.
\end{enumerate}
\prob
A complete graph of order $n$ is a graph with $n$ vertices such that every two vertices are connected by an edge.
\begin{enumerate}
\item Draw the complete graphs of order 2, 3, 4, 5, 6.
\item Find out which ones of these graphs are traversable or eulerian.
\item Find a simple rule to decide when a complete graph is traversable or eulerian.
\end{enumerate}
\prob
Any polyhedron can be turned into a planar graph (with no intersecting edges) by simply reproducing its vertices and edges on a plane. Some edges may have to be drawn as non-straight lines in the process.
\begin{enumerate}
\item Draw the graphs of a tetrahedron, a cube and an octahedron.
\item Find out which ones of these three graphs are traversable or eulerian.
\end{enumerate}
\prob
Prove that if a graph is traversable, an eulerian graph can be constructed from it by the addition of a single edge.
\prob
Is the previous property also true if we replace the word ``addition'' by ``deletion'' ?
\prob
We know that a connected graph with no odd vertices contains an eulerian circuit, and a connected graph with exactly two odd vertices contains en eulerian trail. Try to determine what special property is exhibited by a connected graph with exactly four odd vertices. Try to prove your answer.
\vfill
{\sl Many of these problems come from \emph{Introductory Graph Theory}, by Gary Chartrand}
\end{document}