\documentclass{article}% \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{graphicx} \usepackage{color}% \setcounter{MaxMatrixCols}{30} %TCIDATA{OutputFilter=latex2.dll} %TCIDATA{Version=5.00.0.2552} %TCIDATA{CSTFile=40 LaTeX article.cst} %TCIDATA{Created=Thursday, August 21, 2008 14:03:59} %TCIDATA{LastRevised=Monday, September 15, 2014 14:08:16} %TCIDATA{} %TCIDATA{} %TCIDATA{} %TCIDATA{Language=American English} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \begin{document} \title{Math 443/543 Graph Theory Notes } \author{David Glickenstein} \maketitle \section{Introduction} We will begin by considering several problems which may be solved using graphs, directed graphs (digraphs), and networks. Problem 1:\ The K\"{o}nigsberg Bridge Problem. The city of K\"{o}nigsberg has a river with two islands and seven bridges. The question is whether one can traverse each bridge exactly once. This is a classical problem solved by Euler in the 1700s. Problem 2: Coloring maps. Given a map of a continent, how many colors does one need to color each country so that it has a different color than each of its neighbors? It turns out the answer is 4, but the proof is extremely difficult. We will prove that 5 is sufficient, which is a weaker result. Problem 3: Ranking pages on the internet. The internet is a (directed)\ graph. How can one rank the importance of all pages on the internet? One answer is the PageRank algorithm, used by google for returning results of internet searches. These are just some of the problems we will investigate in the course of the semester. The formalism of graphs, directed graphs, and networks will serve as a way to model many different situations, and then we will develop techniques devoted to these abstract models. This is very much like when you learn to solve problem using algebra or calculus by converting the problems into equations, and then learning to solve the equations. \section{This course} See the syllabus for information about this course. \section{What is a graph, digraph, and a network} We begin with some examples of a graph and then try to find a definition. \begin{example} Suppose we have 4 teams: Germany, Ghana, Portugal, USA. Each team plays each other. \end{example} \begin{example} Suppose we have 4 teams playing a single elimination tournament. \end{example} \begin{example} Suppose we have a graph connecting people to their classes. \end{example} \begin{example} Suppose we have a graph connecting people to the fields of their classes \end{example} \begin{example} Suppose we have a graph showing which people know each other \end{example} \begin{example} Suppose we have a graph showing actors and those who have appeared in the same movie \end{example} \begin{example} Graphs arising from polyhedra. \end{example} \begin{example} Graphs showing how water serves houses. \end{example} \begin{example} Graphs showing which websites are linked to which. \end{example} \begin{example} Graphs showing which countries share borders with which other countries.\bigskip \end{example} \bigskip \begin{definition} [Chartrand]A graph $G$ is a finite, nonempty set $V$ together with a relation $R$ on $V$ which is: \begin{enumerate} \item irreflexive, i.e., $\left( v,v\right) \notin R$ for any $v\in V,$ and \item symmetric, i.e., $\left( v,w\right) \in R$ if and only if $\left( w,v\right) \in R.$ \end{enumerate} \end{definition} Note: a relation $R$ on a set $V$ is a subset of $V\times V$ (ordered pairs of elements in $V$). \begin{definition} [Bondy and Murty]A graph $G$ is a triple $\left( V\left( G\right) ,E\left( G\right) ,\psi_{G}\right)$ where $V\left( G\right)$ and $E\left( G\right)$ are disjoint sets and $\psi_{G}:E\left( G\right) \rightarrow Sym\left( V\left( G\right) ,V\left( G\right) \right)$ is a map from $E\left( G\right)$ to unordered pairs of vertices. The map $\psi_{G}$ is called the incidence map. \end{definition} Often we will consider $G=\left( V,E\right) ,$ where in this case, we identify $E$ and $\psi_{G}\left( E\right) .$ \begin{definition} In these two definitions, elements of $V$ are called \emph{vertices} and elements of $E$ are called \emph{edges}. \end{definition} Why are these definitions the same? Given the second definition, we simply let $V=V\left( G\right)$ and $R=% %TCIMACRO{\dbigcup \limits_{e\in E\left( G\right) }}% %BeginExpansion {\displaystyle\bigcup\limits_{e\in E\left( G\right) }} %EndExpansion \left[ \psi_{G}\left( e\right) \right] _{1}\cup\left[ \psi_{G}\left( e\right) \right] _{2},$ where $\left[ \psi_{G}\left( e\right) \right] _{1}$ and $\left[ \psi _{G}\left( e\right) \right] _{2}$ are the two ways to order the unordered pairs. Given the first definition, we simply let $E\left( G\right)$ be the unordered pairs corresponding to elements of $R,$ and let $\psi_{G}$ be, essentially, the identity. BUT: there is a difference. Bondy and Murty allow for multiple edges between the same vertices and for edges which start and end at the same vertex! This is an example of how the definition of a graph is not entirely consistent from one place to the next and one must be careful. Some graph terminology: \begin{definition} The order of a graph is the number of vertices, i.e., $\left\vert V\right\vert =\left\vert V\left( G\right) \right\vert .$ \end{definition} \begin{definition} The size of a graph is the number of edges, i.e., $\left\vert E\right\vert =\left\vert E\left( G\right) \right\vert$ \end{definition} We will usually denote edges as $uv,$ with the understanding that $uv=vu.$ In the Chartrand definition, this means that both $\left( u,v\right)$ and $\left( v,u\right)$ are in $R.$ Note, it is possible for the size to be zero, but not the order! We often denote a graph by a diagram, and will often refer to the diagram as the graph itself. Notice that two different diagrams may correspond to the same graph!! \emph{In general, I prefer the description in BM, but will often assume the graph is entirely given by the vertices and edges, unless we are interested graphs with multiple edges between the vertices, in which case we will need the whole definition. We will also generally assume that graphs do not have loops (edges which begin and end at the same vertex).} Some more terminology: \begin{definition} Suppose $u,v,w\in V$ and $uv=e\in E$ and $uw\notin E.$ Then: \begin{itemize} \item We say $e$ \emph{joins} $u$ and $v.$ \item We say $u$ and $v$ are \emph{adjacent} vertices and $u$ and $w$ are \emph{nonadjacent} vertices. \item We say that $u$ and $v$ are \emph{incident} with (or to or on) $e.$ \item If $uv^{\prime}=e^{\prime}\in E$ and $v\neq v^{\prime},$ then we say that $e$ and $e^{\prime}$ are \emph{adjacent} edges. \end{itemize} \end{definition} For completeness now, we define digraphs and networks. \begin{definition} A \emph{directed graph, or digraph}, is a vertex set together with an irreflexive relation. This is the same as saying that edges are ordered pairs instead of unordered pairs. \end{definition} Note, if a digraph is symmetric, it can be represented as a graph. \begin{definition} A \emph{network} is a graph $G$ together with a map $\phi:E\rightarrow \mathbb{R}$. The function $\phi$ may represent the length of an edge, or conductivity, or cross-sectional area or many other things. \end{definition} \section{Isomorphism of graphs} \subsection{Equivalence relations} Studying all possible graphs is a daunting task, since it would require us to consider all finite sets! A usual technique in mathematics is to partition large sets like this using an equivalence relation. See A.3 in Chartrand for this material. \begin{definition} An equivalence relation $R$ on a set $S$ is a subset of $S\times S$ satisfying: \begin{enumerate} \item reflexivity: $\left( x,x\right) \in R$ for every $x\in S,$ \item symmetry: $\left( x,y\right) \in R$ if and only if $\left( y,x\right) \in R,$ and \item transitivity: if $\left( x,y\right) \in R$ and $\left( y,z\right) \in R$ then $\left( x,z\right) \in R.$ \end{enumerate} \end{definition} Note that sometimes denote $\left( x,y\right) \in R$ by $x$ $R$ $y$ or $x\sim y.^{\prime}$ \begin{example} The relation $<$ on the set $\mathbb{R}$ is not an equivalence relation because it is neither reflexive or symmetric (it is transitive!) \end{example} \begin{example} The relation $\leq$ on the set $\mathbb{R}$ is not an equivalence relation because it is not symmetric (it is reflexive and transitive). \end{example} \begin{example} The relation $=$ on the set $\mathbb{R}$ is an equivalence relation. \end{example} \begin{example} The relation \textquotedblleft is equal modulo 2\textquotedblright\ on the set $\mathbb{Z}$ of integers is an equivalence relation. \end{example} \begin{example} The relation defining a graph is not an equivalence relation since it is not reflexive and may not be transitive. \end{example} \begin{example} The relation \textquotedblleft is parallel to\textquotedblright\ on the set of lines in the plane is an equivalence relation. \end{example} The importance of equivalence relations is that they partition the set $S$ into pieces. \begin{definition} The equivalence class of $x,$ usually written as $\left[ x\right]$ or $\left[ x\right] _{R},$ is defined as $\left[ x\right] =\left\{ y\in S:\left( x,y\right) \in R\right\} .$ \end{definition} Note that $\left[ x\right] =\left[ y\right]$ if and only if $\left( x,y\right) \in R,$ i.e., $x$ is equivalent to $y.$ The importance of equivalence relations is that they form a partition. \begin{definition} Let $S$ be a set and let $A_{1},A_{2},\ldots,A_{n}$ be nonempty, disjoint subsets of $S.$ The set $P=\left\{ A_{1},\ldots,A_{n}\right\}$ is a \emph{partition} if $S=A_{1}\cup\cdots\cup A_{n}.$ \end{definition} \begin{example} The set $\left\{ E,O\right\}$ where $E$ are even integers and $O$ are odd integers is a partition of the integers $\mathbb{Z}$. \end{example} \begin{example} Consider $S=\left\{ 1,2,3\right\} .$ The following are partitions of $S$: $P_{1}=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\} \right\} ,$ $P_{2}=\left\{ \left\{ 1,3\right\} ,\left\{ 2\right\} \right\} ,$ $P_{3}=\left\{ \left\{ 1,2,3\right\} \right\} .$ The following sets are not partitions: $Q_{1}=\left\{ \left\{ 1\right\} ,\left\{ 2\right\} \right\} ,$ $Q_{2}=\left\{ \left\{ 1,2\right\} ,\left\{ 2,3\right\} \right\} ,$ $Q_{3}=\left\{ \left\{ 1\right\} ,\left\{ 1,2,3\right\} \right\} .$ \end{example} \begin{proposition} For any equivalence relation $R$ on a set $S,$ the set of equivalence classes $P=\left\{ \left[ x\right] :x\in S\right\}$ form a partition. \end{proposition} Note that we mean $P$ contains one copy of the equivalence class $\left[ x\right] ,$ not one for each $x\in S.$ \begin{proof} We need to show that the equivalence classes are nonempty, disjoint and that their union is all of $S.$ The latter is clearly true, since $S=% %TCIMACRO{\dbigcup \limits_{x\in S}}% %BeginExpansion {\displaystyle\bigcup\limits_{x\in S}} %EndExpansion \left[ x\right] .$ By reflexivity, we know that $x\in\left[ x\right] ,$ so equivalent classes are nonempty. In order to show they are disjoint, we see that if $y\in\left[ x\right] \cap\left[ x^{\prime}\right] ,$ then $\left( x,y\right) \in R$ and $\left( y,x^{\prime}\right) \in R,$ so by transitivity, $\left( x,x^{\prime}\right) \in R$ and hence $\left[ x\right] =\left[ x^{\prime }\right] .$ Thus, for any two elements, their equivalence classes are either the same or disjoint. \end{proof} \subsection{Isomorphism} We are now ready to consider a particular equivalence relation on graphs, isomorphism. We would like it to encapsulate when two graphs which are technically different should have all of the same \textquotedblleft graph theoretic\textquotedblright\ properties. \begin{definition} The graphs $G=\left( V,E\right)$ and $G^{\prime}=\left( V^{\prime },E^{\prime}\right)$ are \emph{isomorphic} if there is a bijection% $\phi:V\rightarrow V^{\prime}%$ such that $vw\in E\text{ if and only if }\phi\left( v\right) \phi\left( w\right) \in E^{\prime}.$ The map $\phi$ is called an \emph{isomorphism}. Since $\phi$ induces a map on edges as well, we can refer to $\phi:G\rightarrow G^{\prime}$ as the isomorphism as well. \end{definition} \begin{remark} A map $\phi:A\rightarrow B$ is a bijection if there exists another map $\phi^{-1}:B\rightarrow A$ such that $\phi^{-1}\circ\phi:A\rightarrow A$ is the identity and $\phi\circ\phi^{-1}:B\rightarrow B$ is the identity. It is well-known that $\phi$ is a bijection if and only if it is \begin{enumerate} \item one-to-one (or injective): if $\phi\left( x\right) =\phi\left( y\right)$ then $x=y,$ and \item onto (or surjective): $\phi\left( A\right) =B.$ \end{enumerate} For more information, see Chartrand A.4. \end{remark} \begin{remark} In the BM definition, one may have multiple edges with the same vertices, so the above definition is not sufficient. Instead, we need to have two bijections, $\phi_{V}:V\rightarrow V^{\prime}$ and $\phi_{E}:E\rightarrow E^{\prime},$ such that $\psi_{G^{\prime}}\left( \phi_{E}\left( e\right) \right) =\phi_{V}\left( u\right) ~\phi_{V}\left( v\right) \text{ if and only if }\psi_{G}\left( e\right) =uv.$ For directed graphs, one needs to take into account the directions. For a network, one has the notion of an isometry, which is an isomorphism that preserves weights. \end{remark} Show examples. \begin{proposition} The relation \textquotedblleft is isomorphic to\textquotedblright\ is an equivalence relation. \end{proposition} \begin{proof} We need to show the following: \begin{enumerate} \item Reflexive: yes, $G$ is isomorphic to $G$ taking the identity map as $\phi.$ \item Symmetric: yes, if $\phi$ is an isomorphism from $G$ to $G^{\prime}$, it is a bijection and hence has an inverse, and thus $\phi^{-1}$ is an isomorphism from $G^{\prime}$ to $G.$ \item Transitive: yes, if $\phi$ is an isomorphism from $G$ to $G^{\prime}$ and $\phi^{\prime}$ is an isomorphism from $G^{\prime}$ to $G^{\prime\prime}.$ Then we claim that $\phi^{\prime\prime}=\phi^{\prime}\circ\phi$ is an isomorphism from $G$ to $G^{\prime\prime}.$ Certainly, it is a bijection, since it has inverse $\left( \phi^{\prime\prime}\right) ^{-1}=\phi^{-1}% \circ\left( \phi^{\prime}\right) ^{-1}.$ Also, we see that $vw\in E$ if and only if $\phi\left( v\right) \phi\left( w\right) \in E^{\prime}$ if and only if $\phi^{\prime}\circ\phi\left( v\right) ~\phi^{\prime}\circ \phi\left( w\right) =\phi^{\prime\prime}\left( v\right) ~\phi ^{\prime\prime}\left( w\right) \in E^{\prime\prime}.$ \end{enumerate} \end{proof} In order to show two graphs are isomorphic, one must find an isomorphism. How do we show two graphs are not isomorphic? \subsection{Easy invariants of graphs} We are looking for properties which are preserved by isomorphism. That way, if we find two graphs with different such properties, they cannot be isomorphic, otherwise the isomorphism would imply that they have the same property! The first such property is the degree. \begin{definition} The \emph{degree} of a vertex $v,$ denoted $\deg_{G}v$ or $\deg v,$ is the number of edges incident with $v.$ \end{definition} Examples of graphs with vertices of different degrees. \begin{proposition} If $\phi:G\rightarrow G^{\prime}$ is an isomorphism, then $\deg_{G}% v=\deg_{G^{\prime}}\phi\left( v\right)$ for each $v\in V\left( G\right) .$ \end{proposition} Note this implies that the set of vertex degrees for each graph must be the same. \begin{proof} Since $\phi$ is an isomorphism, we see that for each edge $vw\in E\left( G\right) ,$ where $v$ is the given vertex and $w$ varies, there is an edge $\phi\left( v\right) ~\phi\left( w\right) \in E\left( G^{\prime}\right) ,$ and thus $\deg_{G}v\leq\deg_{G^{\prime}}\phi\left( v\right) .$ Using the isomorphism $\phi^{-1},$ we see that $\deg_{G^{\prime}}v^{\prime}\leq\deg_{G}\phi^{-1}\left( v^{\prime}\right)$ for any $v^{\prime}\in V\left( G^{\prime}\right) .$ Taking $v^{\prime}% =\phi\left( v\right)$ (which we can do since $\phi$ is a bijection!) we see that $\deg_{G^{\prime}}\phi\left( v\right) \leq\deg_{G}v.$ Thus, we must have that $\deg_{G^{\prime}}\phi\left( v\right) =\deg_{G}v.$ \end{proof} Show examples of non-isomorphic graphs using degree. Here is an example of nonisomorphic graphs with the same degree sequence: \input{C:/Users/glickenstein/Documents/teaching/2014-2015/math443/nonisomorphicgraphs2.pdf_tex} \begin{definition} A $\left( p,q\right)$\emph{-graph} is a graph with order $p$ and size $q.$ \end{definition} \begin{theorem} If $G$ is a $\left( p,q\right)$-graph and $V\left( G\right) =\left\{ v_{1},\ldots,v_{p}\right\} ,$ then $\sum_{i=1}^{p}\deg_{G}\left( v_{i}\right) =2q.$ \end{theorem} \begin{proof} In the left sum, for each vertex we count the edges incident on it. Since each edge is incident on two vertices and each vertex is counted, we get the result. \end{proof} Note that this is quite a restriction on the degrees of vertices, i.e., we cannot just assign degree numbers arbitrarily and hope that there is a graph with that collection of degrees. \begin{definition} We say a vertex is \emph{even} or \emph{odd} depending on whether its degree is even or odd. \end{definition} \begin{theorem} Every graph has an even number of odd vertices. \end{theorem} \begin{proof} If there are no odd vertices, then there are an even number of odd vertices. Suppose $V\left( G\right) =\left\{ v_{1},\ldots,v_{p}\right\} ,$ and suppose the vertices $\left\{ v_{1},\ldots,v_{n}\right\}$ are odd and $\left\{ v_{n+1},\ldots,v_{p}\right\}$ are even (there may be none). We look at the theorem, and see that $\sum_{i=1}^{n}\deg_{G}v_{i}+\sum_{j=n+1}^{p}\deg_{G}v_{j}=2q.$ Recall that the sum of an even number of odd numbers is even and the sum of an odd number of odd numbers is odd. any sum of even numbers is even. Thus we get that $\sum_{i=1}^{n}\deg_{G}v_{i}=2q-\sum_{j=n+1}^{p}\deg_{G}v_{j}%$ has an even number on the right and an odd number on the left if $n$ is odd. Thus $n$ must be even. \end{proof} \begin{remark} How does one prove that the sum of an odd number of odd numbers is odd? One must use induction and we will do it in the homework. \end{remark} \begin{definition} If every vertex has degree $r,$ we say that the graph is $r$\emph{-regular}. A graph is \emph{complete} if every edge is connected to every other edge, or, equivalently, it is $\left( p-1\right)$-regular where $p$ is the order. \end{definition} Draw some complete graphs. \subsection{Enumeration of graphs by order and size} We may try to enumerate the isomorphism classes of graphs by their order and size. Since degree is an invariant, we see that there is only one graph of order 1 (a single vertex), which has size zero. This means that given two graphs $G_{1}$ and $G_{2}$ of size 1, they must be isomorphic. There is one graph with (order,size)=$\left( 2,0\right)$ and one graph with $\left( 2,1\right) .$ There are three $\left( 4,3\right)$ graphs. One can use the pigeonhole principle to see that given any 4 graphs of type $\left( 4,3\right) ,$ two must be isomorphic. The pigeonhole principle can be stated as follows. In the sequel, $\left\lceil x\right\rceil$ is the smallest integer greater than $x,$ also called the ceiling of $x.$ \begin{proposition} [Pigeonhole Principle]If $\left\{ S_{1},S_{2},\cdots,S_{k}\right\}$ is a partition of the set $S$ containing $n$ elements, then there must be at least one $i$ such that $S_{i}$ contains $\left\lceil n/k\right\rceil$ elements. \end{proposition} \begin{proof} Suppose each $S_{i}$ contain fewer than $\left\lceil n/k\right\rceil$ elements. First suppose $n/k$ is an integer. Then the total number of elements in $% %TCIMACRO{\dbigcup \limits_{i=1}^{k}}% %BeginExpansion {\displaystyle\bigcup\limits_{i=1}^{k}} %EndExpansion S_{i}%$ is less than $k\left\lceil n/k\right\rceil =n.$ Hence the union is a strict subset of $S,$ and thus the set is not a partition. If $n/k$ is not an integer, then each set contains at most $\left\lceil n/k\right\rceil -1=\left( n-m\right) /k$ elements, where \$1\leq m