\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}

\begin{document}

\module{Planar graphs}{2}{21}{2 periods}
\en\nocouleur

\prereq{Basic notions and vocabulary about graphs.}

\object{\begin{itemize}
        \item Discover the concept of planar graphs.
	\item Use the main results about planar graphs to solve a few problems.
	\end{itemize}}

\mater{\begin{itemize}
	\item Lesson.
	\item Problems.
	\item Beamer.
	\end{itemize}}

\modpart{The three houses and three utilities problem}{10 mins}

The problem of the three houses and three utilities is presented to the students. They have 10 minutes to try to solve
it.

\begin{quote}
Suppose we have three houses and three utility outlets (electricity, gas and water) situated as shown on the picture
below. Is it possible to connect each utility to each of the three houses without the lines or mains crossing ?
\end{quote}

\modpart{Planar graphs : a short introduction}{15 mins}

The main notions and results about planar graphs are presented by the teacher with a beamer. Students are handed out a
lesson at the end of the presentation

\modpart{Planar graphs : a few problems}{Remaining time}

Working by pairs or groups of three, students have to solve a few problems about planar graphs.


\pagebreak

\moddocdis{Planar graphs}{2}{21}{Lesson}

A \emph{planar} graph is a graph that can be drawn in the plane in such a way that no two edges intersect except at a
vertex. A \emph{plane} graph is a graph that is actually drawn with no intersecting edges.


\begin{center}
\begin{tabular}{ccc}
Plane & Planar & Non-planar \\
\includegraphics[width=4cm]{s02e21/plane.eps} &
\includegraphics[width=4cm]{s02e21/planar.eps} &
\includegraphics[width=4cm]{s02e21/nonplanar.eps} \\
\end{tabular}
\end{center}

Let $G$ be a planar graph. Its edges define \emph{regions} of the plane. The vertices and edges that are incident to a
region make up its \emph{boundary}. For example, the planar graph shown as an example defines 3 regions of the plane :
the outer region must always be counted.

\bigskip

When $G$ is a planar graph, we usually denote $p$ its number of vertices, $q$ its number of edges and $r$ its numbers of
regions.

\bigskip

\theo{Euler's formula}{Let $G$ be a connected plane graph with $p$ vertices, $q$ edges and $r$ regions. Then 
$$p-q+r=2.$$}


\theo{}{Let $G$ be a connected plane graph with $p$ vertices, $q$ edges, where $p\geq 3$. Then 
$$q\leq 3p-6.$$}

\pagebreak

\moddocdis{Planar graphs}{2}{21}{Problems}

\newcounter{prob}
\newcommand{\prob}{\stepcounter{prob}\subsection*{Problem \arabic{prob}}}


\prob
Show that the graphs of the tetrahedron, the cube and the octahedron are planar.

\prob
Draw all possible plane graphs with 1, 2 or 3 vertices.

\prob
Draw a non planar graph with 8 vertices.

\prob
Use polydrons to build a dodecahedron and an icosahedron, then draw plane graphs for these two solids.


\prob
For what values of $n$ is the complete graph $K_n$ planar ? For each value of $n$ such that it is so, draw $K_n$ as a
symmetric plane graph.

\prob
A graph can be obtained from any geographic map by replacing every region by a vertex, and connecting two vertices by an
edge exactly when the two regions share a border segment (not just a corner).
\begin{center}
\includegraphics[width=12cm]{s02e21/maptograph.eps}
\end{center}
\begin{enumerate}
\item What special property exhibits any graph built in this way ?
\item Restate in the context of graph theory the famous Four color Theorem : ``Given any separation of a plane into
contiguous regions, called a map, the regions can be colored using at most four colors so that no two adjacent regions
have the same color.''
\end{enumerate}


\prob
Use graph theory and planar graphs to re-state the three houses problem.

\prob
Let $K_{3,3}$ be the complete bipartite graph shown below. The aim of this exercise is to prove that $K(3,3)$ is not
planar.
\begin{center}
\includegraphics[width=6cm]{s02e21/K33.eps}
\end{center}
As usual, we call $p$ the number of vertices of the graph, $q$ its number of edges and $r$ the number of regions defined
by its edges. Moreover, we sum the number of edges lying on the boundary of each region, for all regions of $K(3,3)$,
and denote this number $N$.
\begin{enumerate}
\item Give the value of $p$ and $q$ for $K_{3,3}$.
\item Suppose that $K_{3,3}$ is planar. Then, deduce from Euler's formula the value of $r$ for any plane representation
of this graph.
\item Prove that no representation of $K_{3,3}$ can contain a triangle. Deduce from this fact an inequality about $N$
and $r$.
\item Explain why $N\leq 2q=18$.
\item Deduce from the previous questions an upper bound for $r$.
\item Conclude.
\end{enumerate}


\pagebreak

\moddocdis{Planar graphs}{2}{21}{Solutions}

\setcounter{prob}{0}


\prob
To show that the graphs of the tetrahedron, the cube and the octahedron are planar, we just have to draw them plane
graphs of these three solids. These plane graphs are shown below.
\begin{center}
\psset{xunit=0.7cm,yunit=0.7cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-3.56,-2.06)(15.42,4.16)
\psline(-2,1)(0,3)
\psline(0,3)(2,1)
\psline(2,1)(0,-1)
\psline(0,-1)(-2,1)
\psline(0,-1)(0,3)
\parametricplot{1.1760052070951352}{5.107180100084451}{1*2.17*cos(t)+0*2.17*sin(t)+-0.83|0*2.17*cos(t)+1*2.17*sin(t)+1}
\psline(4,3)(4,-1)
\psline(4,-1)(8,-1)
\psline(8,-1)(8,3)
\psline(8,3)(4,3)
\psline(5,2)(7,2)
\psline(7,2)(7,0)
\psline(7,0)(5,0)
\psline(5,0)(5,2)
\psline(5,2)(4,3)
\psline(5,0)(4,-1)
\psline(7,0)(8,-1)
\psline(7,2)(8,3)
\psline(10,3)(14,3)
\psline(10,3)(11,1)
\psline(11,1)(13,1)
\psline(13,1)(14,3)
\psline(11,1)(12,2)
\psline(12,2)(13,1)
\psline(12,2)(14,3)
\psline(10,3)(12,2)
\psline(12,-1)(11,1)
\psline(13,1)(12,-1)
\parametricplot{2.498091544796509}{4.71238898038469}{1*2.5*cos(t)+0*2.5*sin(t)+12|0*2.5*cos(t)+1*2.5*sin(t)+1.5}
\parametricplot{-1.5707963267948966}{0.6435011087932844}{1*2.5*cos(t)+0*2.5*sin(t)+12|0*2.5*cos(t)+1*2.5*sin(t)+1.5}
\psdots(-2,1)
\psdots(0,3)
\psdots(2,1)
\psdots(0,-1)
\psdots(4,3)
\psdots(4,-1)
\psdots(8,-1)
\psdots(8,3)
\psdots(5,2)
\psdots(7,2)
\psdots(7,0)
\psdots(5,0)
\psdots(10,3)
\psdots(14,3)
\psdots(11,1)
\psdots(13,1)
\psdots(12,2)
\psdots(12,-1)
\end{pspicture*}
\end{center}


\prob
There are 2 plane graphs with 1 vertex:\\
\begin{center}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-0.98,0.6)(3.78,2.38)
\pscircle(2.94,1.5){0.46}
\psdots(-0.38,1.48)
\psdots(3.4,1.48)
\end{pspicture*}
\end{center}

There are 6 plane graphs with 2 vertices:\\
\begin{center}
\psset{xunit=0.5cm,yunit=0.5cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2.82,-1.1)(18.52,5.22)
\pscircle(9.5,3.98){0.25}
\pscircle(13.5,3.98){0.25}
\pscircle(17.46,3.96){0.23}
\psline(-2,0)(1,0)
\psline(9,0)(6,0)
\psline(14,0)(17,0)
\pscircle(9.48,0.02){0.24}
\pscircle(13.48,0.02){0.26}
\pscircle(17.52,0){0.26}
\psdots(-2,4)
\psdots(1,4)
\psdots(6,4)
\psdots(9,4)
\psdots(14,4)
\psdots(17,4)
\psdots(-2,0)
\psdots(1,0)
\psdots(6,0)
\psdots(9,0)
\psdots(14,0)
\psdots(17,0)
\psdots(6,0)
\psdots(17,0)
\end{pspicture*}
\end{center}

\newpage


There are 20 plane graphs with 3 vertices:\\
\begin{center}
\psset{xunit=0.55cm,yunit=0.55cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt
2,arrowinset=0.25}
\begin{pspicture*}(-4.79,-18.6)(19.26,7.01)
\pscircle(4,5.58){0.32}
\pscircle(9.97,5.54){0.3}
\pscircle(11.56,3.01){0.31}
\pscircle(15.98,5.54){0.3}
\pscircle(14.51,3.03){0.27}
\pscircle(17.49,2.97){0.27}
\pscircle(3.98,0.51){0.28}
\pscircle(10.01,0.51){0.28}
\pscircle(11.52,-2){0.29}
\pscircle(16.02,0.49){0.27}
\pscircle(14.49,-2){0.28}
\pscircle(17.51,-2.02){0.28}
\psline(-3,-2)(-2,0)
\psline(3,-2)(4,0)
\psline(9,-2)(10,0)
\psline(15,-2)(16,0)
\psline(-3,-7)(-1,-7)
\pscircle(-2.02,-4.51){0.27}
\psline(3,-7)(4,-5)
\psline(4,-5)(5,-7)
\psline(9,-7)(10,-5)
\psline(10,-5)(11,-7)
\psline(15,-7)(16,-5)
\psline(17,-7)(16,-5)
\psline(-3,-12)(-2,-10)
\psline(-1,-12)(-2,-10)
\pscircle(10.01,-4.49){0.28}
\pscircle(14.51,-7.01){0.27}
\pscircle(-1.98,-9.52){0.27}
\pscircle(-3.49,-12){0.27}
\psline(3,-12)(4,-10)
\psline(4,-10)(5,-12)
\psline(9,-12)(10,-10)
\psline(10,-10)(11,-12)
\pscircle(2.49,-11.98){0.28}
\pscircle(5.48,-12.02){0.26}
\pscircle(9.99,-9.5){0.28}
\pscircle(8.48,-12){0.29}
\pscircle(11.5,-12){0.28}
\psline(15,-12)(16,-10)
\psline(16,-10)(17,-12)
\psline(15,-12)(17,-12)
\psline(-3,-17)(-2,-15)
\psline(-2,-15)(-1,-17)
\psline(-1,-17)(-3,-17)
\psline(3,-17)(4,-15)
\psline(4,-15)(5,-17)
\psline(5,-17)(3,-17)
\psline(9,-17)(10,-15)
\psline(10,-15)(11,-17)
\psline(11,-17)(9,-17)
\pscircle(-2,-14.49){0.28}
\pscircle(2.49,-17.01){0.28}
\pscircle(4,-14.51){0.27}
\pscircle(9.95,-14.49){0.28}
\pscircle(8.5,-17){0.28}
\pscircle(11.5,-17){0.28}
\psline(15,-17)(16,-15)
\pscircle(16,-14.47){0.29}
\pscircle(14.5,-16.98){0.28}
\psdots(-3,3)
\psdots(-1,3)
\psdots(-2,5)
\psdots(3,3)
\psdots(5,3)
\psdots(4,5)
\psdots(9,3)
\psdots(11,3)
\psdots(10,5)
\psdots(15,3)
\psdots(17,3)
\psdots(16,5)
\psdots(-3,-2)
\psdots(-0.84,-2.02)
\psdots(-2,0)
\psdots(3,-2)
\psdots(5,-2)
\psdots(4,0)
\psdots(9,-2)
\psdots(11,-2)
\psdots(10,0)
\psdots(15,-2)
\psdots(17,-2)
\psdots(16,0)
\psdots(-2,-5)
\psdots(-3,-7)
\psdots(-1,-7)
\psdots(3,-7)
\psdots(5,-7)
\psdots(4,-5)
\psdots(9,-7)
\psdots(11,-7)
\psdots(10,-5)
\psdots(15,-7)
\psdots(17,-7)
\psdots(16,-5)
\psdots(-2,-10)
\psdots(-3,-12)
\psdots(-1,-12)
\psdots(4,-10)
\psdots(3,-12)
\psdots(5,-12)
\psdots(10,-10)
\psdots(9,-12)
\psdots(11,-12)
\psdots(16,-10)
\psdots(15,-12)
\psdots(17,-12)
\psdots(3,-17)
\psdots(5,-17)
\psdots(4,-15)
\psdots(9,-17)
\psdots(11,-17)
\psdots(10,-15)
\psdots(17,-7)
\psdots(-3,-17)
\psdots(-1,-17)
\psdots(-2,-15)
\psdots(15,-17)
\psdots(17,-17)
\psdots(16,-15)
\end{pspicture*}
\end{center}


\prob
A simple example of non planar graph with 8 vertices is the complete graph $K_8$:\\
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(1.04,-0.44)(6.9,5.16)
\psline[linecolor=qrqrqr](3,0)(5,0)
\psline[linecolor=qrqrqr](5,0)(6.41,1.41)
\psline[linecolor=qrqrqr](6.41,1.41)(6.41,3.41)
\psline[linecolor=qrqrqr](6.41,3.41)(5,4.83)
\psline[linecolor=qrqrqr](5,4.83)(3,4.83)
\psline[linecolor=qrqrqr](3,4.83)(1.59,3.41)
\psline[linecolor=qrqrqr](1.59,3.41)(1.59,1.41)
\psline[linecolor=qrqrqr](1.59,1.41)(3,0)
\psline[linecolor=qrqrqr](3,0)(1.59,3.41)
\psline[linecolor=qrqrqr](3,0)(3,4.83)
\psline[linecolor=qrqrqr](3,0)(5,4.83)
\psline[linecolor=qrqrqr](3,0)(6.41,3.41)
\psline[linecolor=qrqrqr](3,0)(6.41,1.41)
\psline[linecolor=qrqrqr](1.59,1.41)(3,4.83)
\psline[linecolor=qrqrqr](1.59,1.41)(5,4.83)
\psline[linecolor=qrqrqr](1.59,1.41)(6.41,3.41)
\psline[linecolor=qrqrqr](1.59,1.41)(6.41,1.41)
\psline[linecolor=qrqrqr](1.59,1.41)(5,0)
\psline[linecolor=qrqrqr](1.59,3.41)(5,0)
\psline[linecolor=qrqrqr](1.59,3.41)(6.41,1.41)
\psline[linecolor=qrqrqr](1.59,3.41)(6.41,3.41)
\psline[linecolor=qrqrqr](1.59,3.41)(5,4.83)
\psline[linecolor=qrqrqr](3,4.83)(5,0)
\psline[linecolor=qrqrqr](3,4.83)(6.41,1.41)
\psline[linecolor=qrqrqr](3,4.83)(6.41,3.41)
\psline[linecolor=qrqrqr](5,4.83)(5,0)
\psline[linecolor=qrqrqr](5,4.83)(6.41,1.41)
\psline[linecolor=qrqrqr](6.41,3.41)(5,0)
\psdots[linecolor=qrqrqr](3,0)
\psdots[linecolor=qrqrqr](5,0)
\psdots[linecolor=qrqrqr](6.41,1.41)
\psdots[linecolor=qrqrqr](6.41,3.41)
\psdots[linecolor=qrqrqr](5,4.83)
\psdots[linecolor=qrqrqr](3,4.83)
\psdots[linecolor=qrqrqr](1.59,3.41)
\psdots[linecolor=qrqrqr](1.59,1.41)
\end{pspicture*}
\end{center}

\prob
\begin{multicols}{2}
Plane graph of a dodecahedron :\\
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.6cm,yunit=0.6cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt
2,arrowinset=0.25}
\begin{pspicture*}(-6.56,-2.28)(6.46,8.4)
\psline[linecolor=qrqrqr](0,2)(1,3)
\psline[linecolor=qrqrqr](1,3)(0.36,4.26)
\psline[linecolor=qrqrqr](0.36,4.26)(-1.04,4.04)
\psline[linecolor=qrqrqr](-1.04,4.04)(-1.26,2.64)
\psline[linecolor=qrqrqr](-1.26,2.64)(0,2)
\psline[linecolor=qrqrqr](-1.04,4.04)(-1.91,4.91)
\psline[linecolor=qrqrqr](-1.91,4.91)(-0.73,6.61)
\psline[linecolor=qrqrqr](-0.73,6.61)(0.92,5.36)
\psline[linecolor=qrqrqr](0.92,5.36)(0.36,4.26)
\psline[linecolor=qrqrqr](0.36,4.26)(-1.04,4.04)
\psline[linecolor=qrqrqr](0.36,4.26)(0.92,5.36)
\psline[linecolor=qrqrqr](0.92,5.36)(2.9,4.76)
\psline[linecolor=qrqrqr](2.9,4.76)(2.22,2.81)
\psline[linecolor=qrqrqr](2.22,2.81)(1,3)
\psline[linecolor=qrqrqr](1,3)(0.36,4.26)
\psline[linecolor=qrqrqr](1,3)(2.22,2.81)
\psline[linecolor=qrqrqr](2.22,2.81)(2.26,0.74)
\psline[linecolor=qrqrqr](2.26,0.74)(0.19,0.78)
\psline[linecolor=qrqrqr](0.19,0.78)(0,2)
\psline[linecolor=qrqrqr](0,2)(1,3)
\psline[linecolor=qrqrqr](0,2)(0.19,0.78)
\psline[linecolor=qrqrqr](0.19,0.78)(-1.76,0.1)
\psline[linecolor=qrqrqr](-1.76,0.1)(-2.36,2.08)
\psline[linecolor=qrqrqr](-2.36,2.08)(-1.26,2.64)
\psline[linecolor=qrqrqr](-1.26,2.64)(0,2)
\psline[linecolor=qrqrqr](-1.26,2.64)(-2.36,2.08)
\psline[linecolor=qrqrqr](-2.36,2.08)(-3.61,3.73)
\psline[linecolor=qrqrqr](-3.61,3.73)(-1.91,4.91)
\psline[linecolor=qrqrqr](-1.91,4.91)(-1.04,4.04)
\psline[linecolor=qrqrqr](-1.04,4.04)(-1.26,2.64)
\psline[linecolor=qrqrqr](-3.61,3.73)(-5.21,3.98)
\psline[linecolor=qrqrqr](-5.21,3.98)(-0.98,8.21)
\psline[linecolor=qrqrqr](-0.98,8.21)(-0.73,6.61)
\psline[linecolor=qrqrqr](-0.98,8.21)(4.34,5.5)
\psline[linecolor=qrqrqr](4.34,5.5)(2.9,4.76)
\psline[linecolor=qrqrqr](4.34,5.5)(3.41,-0.41)
\psline[linecolor=qrqrqr](3.41,-0.41)(2.26,0.74)
\psline[linecolor=qrqrqr](-1.76,0.1)(-2.5,-1.34)
\psline[linecolor=qrqrqr](-2.5,-1.34)(3.41,-0.41)
\psline[linecolor=qrqrqr](-2.5,-1.34)(-5.21,3.98)
\psdots[linecolor=qrqrqr](0,2)
\psdots[linecolor=qrqrqr](1,3)
\psdots[linecolor=qrqrqr](0.36,4.26)
\psdots[linecolor=qrqrqr](-1.04,4.04)
\psdots[linecolor=qrqrqr](-1.26,2.64)
\psdots[linecolor=qrqrqr](-3.61,3.73)
\psdots[linecolor=qrqrqr](-1.91,4.91)
\psdots[linecolor=qrqrqr](-0.73,6.61)
\psdots[linecolor=qrqrqr](0.92,5.36)
\psdots[linecolor=qrqrqr](2.9,4.76)
\psdots[linecolor=qrqrqr](2.22,2.81)
\psdots[linecolor=qrqrqr](2.26,0.74)
\psdots[linecolor=qrqrqr](0.19,0.78)
\psdots[linecolor=qrqrqr](-1.76,0.1)
\psdots[linecolor=qrqrqr](-2.36,2.08)
\psdots[linecolor=qrqrqr](-5.21,3.98)
\psdots[linecolor=qrqrqr](-2.5,-1.34)
\psdots[linecolor=qrqrqr](3.41,-0.41)
\psdots[linecolor=qrqrqr](4.34,5.5)
\psdots[linecolor=qrqrqr](-0.98,8.21)
\end{pspicture*}
\end{center}

Plane graph of an icosahedron :\\
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.5cm,yunit=0.5cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-3.35,-5.65)(11.75,10)
\psline[linecolor=qrqrqr](3,-1)(6,-1)
\psline[linecolor=qrqrqr](6,-1)(7.5,1.6)
\psline[linecolor=qrqrqr](7.5,1.6)(6,4.2)
\psline[linecolor=qrqrqr](6,4.2)(3,4.2)
\psline[linecolor=qrqrqr](3,4.2)(1.5,1.6)
\psline[linecolor=qrqrqr](1.5,1.6)(3,-1)
\pscircle[linecolor=qrqrqr](4.5,1.6){3}
\psline[linecolor=qrqrqr](3.97,2.51)(3.97,0.69)
\psline[linecolor=qrqrqr](3.97,0.69)(5.55,1.6)
\psline[linecolor=qrqrqr](5.55,1.6)(3.97,2.51)
\psline[linecolor=qrqrqr](3.97,2.51)(6,4.2)
\psline[linecolor=qrqrqr](5.55,1.6)(6,4.2)
\psline[linecolor=qrqrqr](5.55,1.6)(6,-1)
\psline[linecolor=qrqrqr](6,-1)(3.97,0.69)
\psline[linecolor=qrqrqr](3.97,0.69)(1.5,1.6)
\psline[linecolor=qrqrqr](1.5,1.6)(3.97,2.51)
\psline[linecolor=qrqrqr](3.97,2.51)(3,4.2)
\psline[linecolor=qrqrqr](3.97,0.69)(3,-1)
\psline[linecolor=qrqrqr](5.55,1.6)(7.5,1.6)
\psline[linecolor=qrqrqr](6,4.2)(7.5,6.79)
\psline[linecolor=qrqrqr](7.5,6.79)(3,4.2)
\psline[linecolor=qrqrqr](3,4.2)(-1.49,1.6)
\psline[linecolor=qrqrqr](-1.49,1.6)(1.5,1.6)
\psline[linecolor=qrqrqr](-1.49,1.6)(3,-1)
\psline[linecolor=qrqrqr](3,-1)(7.5,-3.59)
\psline[linecolor=qrqrqr](7.5,-3.59)(6,-1)
\psline[linecolor=qrqrqr](7.5,-3.59)(7.5,1.6)
\psline[linecolor=qrqrqr](7.5,1.6)(7.5,6.79)
\psdots[linecolor=qrqrqr](3,-1)
\psdots[linecolor=qrqrqr](6,-1)
\psdots[linecolor=qrqrqr](7.5,1.6)
\psdots[linecolor=qrqrqr](6,4.2)
\psdots[linecolor=qrqrqr](3,4.2)
\psdots[linecolor=qrqrqr](1.5,1.6)
\psdots[linecolor=qrqrqr](3.97,2.51)
\psdots[linecolor=qrqrqr](3.97,0.69)
\psdots[linecolor=qrqrqr](5.55,1.6)
\psdots[linecolor=qrqrqr](7.5,6.79)
\psdots[linecolor=qrqrqr](-1.49,1.6)
\psdots[linecolor=qrqrqr](7.5,-3.59)
\end{pspicture*}

\end{multicols}



\prob
The complete graph $K_n$ is planar only for $n\leq 4$. These graphs are shown below.
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.8cm,yunit=0.8cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-3.78,0.38)(12.84,5.22)
\psline(0,1)(2,1)
\psline(5,1)(6.02,2.5)
\psline(6.02,2.5)(7,1)
\psline(7,1)(5,1)
\psline(10,3)(12,3)
\psline(12,3)(12,1)
\psline(12,1)(10,1)
\psline(10,1)(10,3)
\psline(10,1)(12,3)
\parametricplot{0.39049343960842875}{4.321895540776261}{
1*1.53*cos(t)+0*1.53*sin(t)+10.58|0*1.53*cos(t)+1*1.53*sin(t)+2.42}
\psdots[linecolor=qrqrqr](-3,1)
\psdots[linecolor=qrqrqr](0,1)
\psdots[linecolor=qrqrqr](2,1)
\psdots[linecolor=qrqrqr](6.02,2.5)
\psdots[linecolor=qrqrqr](5,1)
\psdots[linecolor=qrqrqr](7,1)
\psdots[linecolor=qrqrqr](10,3)
\psdots[linecolor=qrqrqr](12,3)
\psdots[linecolor=qrqrqr](12,1)
\psdots[linecolor=qrqrqr](10,1)
\end{pspicture*}
\end{center}


\prob
\begin{enumerate}
\item Any graph built in this way is plane. Indeed, as frontiers cannot cross each other on a map, edges cannot do it
either in a graph built from a map.
\item In any plane graph, the vertices can can be colored using at most four colors so that no two adjacent vertices
have the same color.
\end{enumerate}


\prob
Consider a graph made of two groups of three vertices, such that each vertex of each group is adjacent to each
vertex of the other group, but to no vertex of the same group. This graph is not planar.

\prob
\begin{enumerate}
\item For $K_{3,3}$, $p=6$ and $q=9$. 
\item For any plane representation of $K_{3,3}$, we would still have $p=6$ and $q=9$. Then, according to Euler's
formula, $p-q+r=2$, so $6-9+r=2$, therefore $r=5$.
\item First, we can notice that $K_{3,3}$ is made of two groups of vertices, each one with three vertices, and
such that each vertex of each group is adjacent to each vertex of the other group, but to no vertex of the same group. 
Now, consider three vertices $A$, $B$, $C$ in $K_{3,3}$. At least two of them must be in the same group. If it's
exactly two, say $A$ and $B$, then these two vertices are not adjacent, so $A$, $B$ and $C$ don't make a triangle. If
the three vertices are in the same group, then none is adjacent to any other, so $A$, $B$ and $C$ don't make a
triangle. Then, no representation of $K_{3,3}$ can contain a triangle.\\ This means that any region in such a plane
graph will be bounded by at least $4$ edges, so $N\geq 4r$.
\item Any edge can bound at most two regions, so $N\leq 2q$. But $q=9$, so $N\leq 2q=18$.
\item We know that $N\geq 4r$ and $N\leq 2q=18$, so $4r\leq N\leq 18$, $4r\leq 18$, $r\leq 3.5$.
\item If question 2 we've seen that if $K_{3,3}$ is planar, then $r$ must be equal to $5$. But in question $5$ we found
that in any representation of $K_{3,3}$, $r\leq 3.5$. These two inequalities contradict each other, so $K_{3,3}$ is not
planar.
\end{enumerate}






\end{document}
