%This macro provides the math text for the second column of page 5
%
%The macro has one parameter:
% 1) The width of the text
\newcommand\TFiveGrapheOne[1]{%
\def\LineOfArray##1##2{##1&{\raggedright ##2}\\}
\parbox[t]{#1}{%
%Space dedicated to the explanation of the graph's
%vocabulary in the tabular environment
\deflength{\HSpace}{.70#1}
\TFiveGraphFontSize
%Since the column is narrow, ragged at right
%produces better spacing
%
\raggedright
\TFiveTitle{Definitions:}
\begin{tabular}{@{}l@{\hspace{.25em}}p{\HSpace}}
\LineOfArray{Loop}{An edge connecting a vertex to itself.}
\LineOfArray{Directed}{Each edge has a direction.}
\LineOfArray{Simple}{Graph with no loops or multi-edges.}
\LineOfArray{Walk}{A sequence $v_0e_1v_1\ldots e_\ell v_\ell$.}
\LineOfArray{Trail}{A walk with distinct edges.}
\LineOfArray{Path}{A trail with distinct vertices.}
\LineOfArray{Connected}{A graph where there exists a path between any two vertices.}
\LineOfArray{Component}{A maximal connected subgraph.}
\LineOfArray{Tree}{A connected acyclic graph.}
\LineOfArray{Free tree}{A tree with no root.}
\LineOfArray{DAG}{Directed acyclic graph.}
\LineOfArray{Eulerian}{Graph with a trail visiting each edge exactly once.}
\LineOfArray{Hamiltonian}{Graph with a cycle visiting each vertex exactly once.}
\LineOfArray{Cut}{A set of edges whose removal increases the number of components.}
\LineOfArray{Cut-set}{A minimal cut.}
\LineOfArray{Cut edge}{A size 1 cut.}
\LineOfArray{k-Connected}{A graph connected with the removal of any $k-1$ vertices.}
\LineOfArray{k-Tough}{$\forall S \subseteq V, S \neq \emptyset$ we have $k\cdot c(G-S) \leq \vert S \vert$.}
\LineOfArray{k-Regular}{A graph where all vertices have degree $k$.}
\LineOfArray{k-Factor}{A $k$-regular spanning subgraph.}
\LineOfArray{Matching}{A set of edges, no two of which are adjacent.}
\LineOfArray{Clique}{A set of vertices, all of which are adjacent.}
\LineOfArray{Ind. set}{A set of vertices, none of which are adjacent.}
\LineOfArray{Vertex cover}{A set of vertices which cover all edges.}
\LineOfArray{Planar graph}{A graph which can be embeded in the plane.}
\LineOfArray{Plane graph}{An embedding of a planar graph.}
\end{tabular}
\TFiveTitle{Planar graphs}
\AdjustSpace{1ex plus .5ex minus .2ex}
\begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
\Fm{\sum_{v\in V} \deg(v) = 2 m}
\end{DisplayFormulae}
\AdjustSpace{1ex plus .5ex minus .2ex}
If $G$ is planar then $n - m + f = 2$, so
\AdjustSpace{1ex plus .5ex minus .2ex}
\begin{DisplayFormulae}{1}{0pt}{4ex plus 1ex minus .5ex}{\SmallChar}{\StyleWithoutNumber}
\Fm{f \leq 2n - 4, \quad m \leq 3 n - 6}
\end{DisplayFormulae}
\AdjustSpace{1ex plus .5ex minus .2ex}
Any planar graph has a vertex with degree $\leq 5$.
