\documentclass{article}
%\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\pagestyle{empty}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.50in}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-.250in}
\setlength{\headheight}{0in}
\setlength{\headsep}{.25in}
\setlength{\topskip}{0in}
\setlength{\textheight}{9.05in}
\setlength{\parindent}{-0.2in}
\font\bigbf = cmbx10 scaled \magstep1
\font\medbf = cmbx10 scaled \magstephalf
\def\C{{\mathbb C}}
\def\Z{{\mathbb Z}}
\def\F{{\mathbb F}}
\def\bF{{\mathbb F}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\P{{\mathbb P}}
\def\N{{\mathbb N}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\sC{{\mathscr C}}
\def\x{{\bold x}}
\def\y{{\bold y}}
\newcommand{\qr}[2]{{\left(\frac{#1}{#2}\right)}}
\newcommand{\cyc}[1]{\left<{#1}\right>}
\newcommand{\nrm}[1]{\left|\left|{#1}\right|\right|}
\def\lcm{{\operatorname{lcm}}}
\def\gcd{{\operatorname{gcd}}}
\def\im{{\operatorname{im}}}
\def\dist{{\operatorname{dist}}}
\def\charpoly{{\operatorname{charpoly}}}
\def\Gal{{\operatorname{Gal}}}
\def\Arr{{\operatorname{Arr}}}
\newcommand{\vy}{\mathbf{y}}
\newcommand{\vc}{\mathbf{c}}
\newcommand{\Int}[2]{{\displaystyle{\int_{#1}^{#2}}}}
\newcommand{\hint}{\textsc{Hint:}\,\,}
\newcommand{\Nul}{\hbox{Nul}\,}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\ii}{\vec{\imath}}
\newcommand{\jj}{\vec{\jmath}}
\newcommand{\kk}{\vec{k}}
\newcommand{\vecc}[1]{\mathbf{#1}}
\def\minpoly{{\operatorname{minpoly}}}
\def\card{{\operatorname{card}}}
% Some useful definitions
\newcommand{\ideal}[1]{\left\langle\, #1 \,\right\rangle}
\newcommand{\bform}[2]{\left\langle\, #1,\,#2\,\right\rangle}
\newcommand{\dquot}[2]{\raise.5ex\hbox{$#1$}\hbox{\Large$/$}\lower.25ex\hbox{$#2$}}
\newcommand{\bigdquot}[2]{\raise1.5ex\hbox{$#1$}\hbox{\Huge$/$}\lower.75ex\hbox{$#2$}}
\def\GL{\operatorname{GL}}
\def\SO{\operatorname{SO}}
\def\O{\operatorname{O}}
\def\PGL{\operatorname{PGL}}
\def\SL{\operatorname{SL}}
\def\PSL{\operatorname{PSL}}
\def\Stab{\operatorname{Stab}}
\def\Aut{\operatorname{Aut}}
\def\Perm{\operatorname{Perm}}
\def\Inn{\operatorname{Inn}}
\def\Out{\operatorname{Out}}
\def\adj{\operatorname{adj}}
\def\SL{\operatorname{SL}}
\def\sgn{\operatorname{sign}}
\def\dm{\operatorname{dim}}
\def\trace{\operatorname{trace}}
\def\rnk{\operatorname{rank}}
\def\Log{\operatorname{Log}}
\def\Arg{\operatorname{Arg}}
\def\Real{\operatorname{Re}}
\def\Im{\operatorname{Im}}
\def\spn{\operatorname{span}}
\def\diam{\operatorname{diam}}
\def\rad{\operatorname{rad}}
\def\domain{\operatorname{dom}}
\def\Hom{\operatorname{Hom}}
\def\Frob{\operatorname{Frob}}
\def\IrrPoly{\operatorname{IrrPoly}}
\def\ML{\operatorname{ML}}
\def\MAP{\operatorname{MAP}}
\def\NN{\operatorname{NN}}
\def\Char{\operatorname{char}}
\def\id{\operatorname{id}}
\def\tr{\operatorname{Tr}}
\def\eps{\varepsilon}
\def\normsub{\trianglelefteq}
\def\Def{\indent {\bf \sc Def:}\:}
\def\Thm{\indent {\bf \sc Thm:}\:}
\def\Prop{\indent {\bf \sc Prop:}\:}
\def\Lma{\indent {\bf \sc Lma:}\:}
\def\Cor{\indent {\bf \sc Cor:}\:}
\def\Fact{\indent {\bf \sc Fact:}\:}
\def\question{\indent {\sc Question:}\:}
\def\v{{\mathbf v}}
\def\u{{\mathbf u}}
\def\vv{{\mathbf v}}
\def\vu{{\mathbf u}}
\def\va{{\mathbf a}}
\def\vb{{\mathbf b}}
\def\vc{{\mathbf c}}
\def\vx{{\mathbf x}}
\def\vy{{\mathbf y}}
\def\vz{{\mathbf z}}
\def\B{{\mathbf B}}
\def\calm{\mathfrak m}
\def\frakp{\mathfrak p}
\DeclareMathOperator*{\argmax}{\operatorname{arg\,max}}
\DeclareMathOperator*{\argmin}{\operatorname{arg\,min}}
\usepackage{fancyhdr, mathrsfs}
\begin{document}
\pagestyle{fancyplain}
\chead[\bigbf Graph Theory Study Guide]{\bigbf Graph Theory Study Guide}
\cfoot[\it Derrick Stolee]{\it Derrick Stolee}
\rfoot[]{\thepage}
\lfoot[\thepage]{}
{\bigbf Chapter 1: Fundamental Concepts}
{\bf Section 1.1: What is a Graph?}
\Def A {\bf graph} $G = (V,E)$, {\bf vertex set} $V(G)$, {\bf edge set} $E(G)$. Each edge has two vertices as {\bf endpoints}.
\Def A {\bf loop} is an edge with equal endpoints. {\bf Multiple edges} are multiple edges with same pair of endpoints. {\bf Simple graphs} have no loops or multiple edges. Vertices $u, v \in V(G)$ are {\bf neighbors} and are {\bf adjacent} when they are endpoints of an edge.
\Def The {\bf complement} $\overline{G}$ of a simple graph $G$ is the simple graph with vertex set $V(G)$ defined by $uv \in E(\overline{G})$ if and only if $uv \notin E(G)$. A {\bf clique} is a set of pairwise adjacent vertices. An {\bf independent set} or {\bf stable set} is a set of pairwise nonadjacent vertices.
\Def A graph $G$ is {\bf bipartite} if $V(G)$ is the union of two disjoint independent sets called {\bf partite sets} of $G$. The pair of partite sets is also called a {\bf bipartition}.
\Def The {\bf chromatic number} of a graph $G$, written $\chi(G)$, is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors. A graph $G$ is $k$-{\bf partite} if $V(G)$ can be expressed as the union of $k$ independent sets.
\Def A {\bf map} is a partition of the plane into connected regions. A graph that can be drawn without edges crossing is {\bf planar}.
\Def A {\bf path} is a simple graph whose vertices can be ordered with vertices adjacent if and only if they are consecutive. A {\bf cycle} is a graph such that the vertices can be ordered on a circle such that vertices are adjacent if and only if they are consecutive in the circle.
\Def A {\bf subgraph} of a graph $G$ is a graph $H$ with $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. A graph is {\bf connected} if every pair of vertices belongs to a path. Otherwise, the graph is {\bf disconnected}.
\Def The {\bf adjacency matrix} $A(G)$ is the $n\times n$ matrix with $a_{i,j}$ the number of edges with endpoints $\{v_i,v_j\}$. The {\bf incidence matrix} is the $n\times m$ matrix with entries $m_{i,j}$ 1 when $v_i$ is an endpoint of $e_j$ and $0$ otherwise. If $v$ is an endpoint of $e$ then they are {\bf incident}.
\Def An {\bf isomorphism} of $G$ to $H$ is a bijection $f:V(G) \to V(H)$ such that $uv \in E(G)$ if and only if $f(u)f(v) \in E(H)$.
\Def A {\bf relation} on a set $S$ is a collection of ordered pairs from $S$. An {\bf equivalence relation} is a relation that is reflexive, symmetric, and transitive.
\Prop On the set of simple graphs, the {\bf isomorphism relation} is an equivalence relation.
\Def An {\bf isomorphism class} of graphs is an equivalence class of graphs under the isomorphism relation.
\Def The path and cycle with $n$ vertices are labeled $P_n$ and $C_n$. A {\bf complete graph} is a simple graph whose vertices are pairwise adjacent, labeled $K_n$. A {\bf complete bipartite graph} or {\bf biclique} is a simple bipartite graph such that two vertices are adjacent if and only if they are in different partite sets, labeled $K_{r,s}$.
\Def A graph is {\bf self-complementary} if $G \cong \overline{G}$. A {\bf decomposition} of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.
\Def {\bf triangle}: $K_3$; {\bf claw}: $K_{1,3}$; {\bf paw}: $K_{1,3}+e$; {\bf kite} $K_4 - e$.
\Def The {\bf Petersen graph} is the simple graph whose vertices are the $2$-element subsets of a $5$-element set and whose edges are the pairs of disjoint 2-element subsets.
\Prop If two vertices are nonadjacent in the Petersen graph, then they have exactly one common neighbor.
\Def The length of a graph's shortest cycle is its {\bf girth}.
\Cor The Petersen graph has girth $5$.
\Def An {\bf automorphism} of a graph $G$ is an isomorphism from $G$ to $G$. A graph $G$ is {\bf vertex-transitive} if for every pair $u,v \in V(G)$ there is an automorphism that maps $u$ to $v$.
{\bf Section 1.2: Paths, Cycles, and Trails}
\Thm ``{\it Strong Principle of Induction}" Let $P(n)$ be a statement with an integer parameter $n$. If the following two conditions hold, then $P(n)$ is true for each positive integer $n$: 1. $P(1)$ is true. 2. For all $n > 1$, ``$P(k)$ is true for $1 \leq k < n$" implies ``$P(n)$ is true."
\Def A {\bf walk} is a list $v_0,e_1,v_1,\dots, e_k,v_k$ of vertices and edges such that for $1 \leq i \leq k$, the edge $e_i$ has endpoints $v_{i-1}$ and $v_i$. A {\bf trail} is a walk with no repeated edge. A $u,v$-{\bf walk}$ or $u,v$-{\bf trail}$ has a first vertex $u$ and a last vertex $v$; these are its {\bf endpoints}. A $u,v$-{\bf path} is a path whose vertices of degree $1$ (the {\bf endpoints}) are $u,v$; the others are {\bf internal vertices}. The {\bf length} of a walk, trail, path, or cycle is its number of edges. A walk or trail is {\bf closed} if the endpoints are the same. A walk is {\bf odd} or {\bf even} if its length is odd or even.
\Lma Every $u,v$-walk contains a $u,v$-path.
\Def A graph $G$ is {\bf connected} if it has a $u,v$-path $\forall u,v \in V(G)$; otherwise $G$ is {\bf disconnected}. If $G$ has a $u,v$-path, then $u$ is {\bf connected to} $v$ in $G$. The {\bf connection relation} on $V(G)$ consists of the ordered pairs $(u,v)$ such that $u$ is connected to $v$.
\Def The {\bf components} of a graph $G$ are its maximal connected subgraphs. A component is {\bf trivial} if it contains no edges; otherwise {\bf non-trivial}. An {\bf isolated vertex} is a vertex of degree $0$.
\Prop Every graph with $n$ vertices and $k$ edges has at least $n-k$ components.
\Def A {\bf cut-edge} or {\bf cut-vertex} of a graph is an edge or vertex whose deletion increases the number of components. An {\bf induced subgraph} is a subgraph obtained by deleting a set of vertices. $G[T]$ (subgraph of $G$ induced by $T$) is formed by deleting the vertex set $V(G) \setminus T$.
\Thm An edge is a cut-edge if and only if it belongs to no cycle.
\Lma Every closed odd walk contains an odd cycle.
\Thm A graph is bipartite if and only if it has no odd cycle.
\Def The {\bf union} of graphs $G_1, \dots, G_k$ written $G_1 \cup \dots \cup G_k$ is the graph with vertex set $\cup_{i=1}^k V(G_i)$ and edge set $\cup_{i=1}^k E_(G_i)$.
\Thm The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k$.
\Def A graph is {\bf Eulerian} if it has a closed trail containing all edges. The closed trail is called a {\bf circuit} when the endpoint is not specified. An {\bf Eulerian circuit} or {\bf Eulerian trail} is a circuit or trail containing all the edges. An {\bf even graph} is a graph with vertex degrees all even. A vertex is {\bf odd}[{\bf even}] when its degree is odd[even].
\Lma If every vertex of a graph $G$ has degree at least $2$ then $G$ contains a cycle.
\Thm A graph $G$ is Eulerian if and only if it has at most one nontrivial component and its vertices all have even degree.
\Prop Every even graph decomposes into cycles.
\Prop If $G$ is a simple graph in which every vertex has degree at least $k$, then $G$ contains a path of length at least $k$. If $k \geq 2$, then $G$ also contains a cycle of length at least $k+1$.
\Prop Every graph with a nonloop edge has at least two vertices that are not cut-vertices.
\Lma In an even graph, every non-extendible trail is closed.
\Thm For a connected nontrivial graph with exactly $2k$ odd vertices, the minimum number of trails that decompose it is $\max\{k,1\}$.
{\bf Section 1.3: Vertex Degrees and Counting}
\Def The {\bf degree} of a vertex $v$ in a graph $G$, written $d_G(v)$ or $d(v)$, is the number of edges incident to $v$, except that each loop at $v$ counts twice. The maximum degree is $\Delta(G)$ and the minimum degree is $\delta(G)$. And $G$ is {\bf regular} if $\Delta(G) = \delta(G)$. It is $k$-{\bf regular} if the common degree is $k$. The {\bf neighborhood} of $v$, written $N_G(v)$ or $N(v)$, is the set of vertices adjacent to $v$.
\Def The {\bf order} of a graph $G$, written $n(G)$, is the number of vertices in $G$. An $n$-{\bf vertex graph} is a graph of order $n$. The {\bf size} of a graph $G$, written $e(G)$ is the number of edges in $G$. The notation $\{n\}$ indicates the set $\{1, \dots, n\}$.
Prop (Degree-Sum Formula): If $G$ is a graph, then $\sum_{v\in V(G)}d(v) = 2e(G).$
\Cor In a graph $G$, the average vertex degree is $\frac{2e(G)}{n(G)}$, and hence $\delta(G) \leq \frac{2e(G)}{n(G)}\leq \Delta(G)$.
\Cor Every graph has an even number of odd vertices. No graph of odd order is regular with odd degree.
\Cor A $k$-regular graph with $n$ vertices has $nk/2$ edges.
\Def The $k$-{\bf dimensional cube} or {\bf hypercube} $Q_k$ is the simple graph whose vertices are the $k$-tuples with entries in $\{0,1\}$ and whose edges are the pairs of $k$-tuples that differ in exactly one position. A $j$-{\bf dimensional subcube} of $Q_k$ is a subgraph of $Q_k$ isomorphic to $Q_j$.
\Prop If $k > 0$, then a $k$-regular bipartite graph has the same number of vertices in each partite set.
\Def A {\bf vertex-deleted subgraph} is a subgraph obtained by deleting a single vertex.
\Prop For a simple graph $G$ with vertices $v_1, \dots, v_n$ and $n \geq 3$, $e(G) = \frac{\sum e(G-v_i)}{n-2}$ and $d_G(v_j) = \frac{\sum e(G-v_i)}{n-2} - e(G-v_j)$.
Conj ({\it Reconstruction Conjecture}): If $G$ is a simple graph with at least three vertices, then $G$ is uniquely determined by the list of (isomorphism classes and multiplicities of) its vertex-deleted subgraphs.
\Prop The minimum number of edges in a connected graph with $n$ vertices is $n-1$.
\Prop If $G$ is a simple $n$-vertex graph with $\delta(G) \geq (n-1)/2$, then $G$ is connected.
\Def The graph obtained by taking the union of graphs $G$ and $H$ with disjoint vertex sets is the {\bf disjoint union} or {\bf sum}, written $G+H$. In general, $mG$ is the graph consisting of $m$ copies of pairwise dijoint copies of $G$.
\Thm Every loopless graph $G$ has a bipartite subgraph with at least $e(G)/2$ edges.
\Def A graph $G$ is $H$-{\bf free} if $G$ has no induced subgraph isomorphic to $H$.
\Thm The maximum number of edges in an $n$-vertex triangle-free simple graph is $\lfloor n^2/4\rfloor$.
\Def The {\bf degree sequence} of a graph is the list of vertex degrees, {\it usually} written nonincreasingly, as $d_1 \geq \cdots \geq d_n$.
\Prop The nonnegative integers $d_1,\dots,d_n$ are the vertex degrees of some graph if and only if $\sum d_i$ is even.
\Def A {\bf graphic sequence} is a list of nonnegative numbers that is the degree sequence of some simple graph. A simple graph with degree sequence $d$ ``realizes" $d$.
\Thm For $n > 1$, an integer list $d$ of size $n$ is graphic if and only if $d'$ is graphic, where $d'$ is obtained from $d$ by deleting its largest element $\Delta (\Delta < n)$ and subtracting $1$ from its $\Delta$ next largest elements. The only $1$-element graphic sequence is $d_1 = 0$.
\Def A {\bf 2-switch} is the replacement of a pair of edges $xy$ and $zw$ in a simple graph by the edges $yz$ and $wx$ given that $yz$ and $wx$ did not appear in the graph originally.
\Thm If $G$ and $H$ are two simple graphs with vertex set $V$, then $d_G(v) = d_H(v)$ for every $v\in V$ if and only if there is a sequence of $2$-switches that transforms $G$ into $H$.
{\bf Section 1.4: Directed Graphs}
\Def A {\bf directed graph} or {\bf digraph} $G$ is a triple consisting of a {\bf vertex set} $V(G)$, an {\bf edge set} $E(G)$, and a function assigning each edge an ordered pair of vertices. The first vertex of the ordered pair is the {\bf tail} or the edge, and the second is the {\bf head}; together they are the {\bf endpoints}. We say that an edge is an edge {\bf from} its tail {\bf to} its head.
\Def In a digraph a {\bf loop} is an edge whose endpoints are equal. {\bf Multiple edges} are edges having the same ordered pair of endpoints. A digraph is {\bf simple} if each ordered pair is the head and tail of at most one edge; one loop may be present at each vertex. In a simple digraph, we write $uv$ for an edge with tail $u$ and head $v$. If there is an edge from $u$ to $v$, then $v$ is a {\bf successor} of $u$, and $u$ is a {\bf predecessor} of $v$.
\Def A digraph is a {\bf path} if it is a simple digraph whose vertices can be linearly ordered so that there is an edge with tail $u$ and head $v$ if and only if $v$ immediately follows $u$ in the vertex ordering. A {\bf cycle} is defined similarly using an ordering of the vertices on a circle.
\Def The {\bf functional digraph} of a function $f: A \to A$ is the simple digraph with vertex set $A$ and edge set $\{ (x,f(x)) | x\in A\}$.
\Def The {\bf underlying graph} of a digraph $D$ is the graph $G$ obtained by treating the edges of $D$ ad unordered pairs; the vertex set and edge set remain the same, and the endpoints of an edge are the same in $G$ as in $D$, but in $G$ they become an unordered pair.
\Def The definitions of {\bf subgraph}, {\bf isomorphism}, {\bf decomposition}, and {\bf union} follow from graphs. In the {\bf adjacency matrix} $A(G)$ of a digraph $G$, the $i,j$ entry is the number of edges from $v_i$ to $v_j$. In the {\bf incidence matrix} $M(G)$ of a loopless digraph $G$, we set $m_{i,j} = +1$ if $v_i$ is the tail of $e_j$ and $m_{i,j} = -1$ if $v_i$ is the head of $e_j$.
\Def A digraph is {\bf weakly connected} if its underlying graph is connected. A digraph is {\bf strongly connected} or {\bf strong} if for each {\it ordered pair} $u,v$ of vertices there is a path form $u$ to $v$. The {\bf strong components} of a digraph are its maximal strong subgraphs.
\Def A {\bf kernel} in the digraph $D$ is a set $S \subseteq V(D)$ such that $S$ induces no edges and every vertex outside $S$ has a successor in $S$.
\Thm Every digraph having no odd cycle has a kernel.
\Def The {\bf outdegree} $d^+(v)$ is the number of edges with tail $v$. The {\bf indegree} $d^-(v)$ is the number of edges with head $v$. The {\bf out-neighborhood} or {\bf successor set} $N^+(v)$ is $\{x \in V(G) | v \to x\}$. The {\bf in-neighborhood} or {\bf predecessor set} $N^-(v)$ is $\{x \in V(G) | x \to v\}$. the minimum and maximum indegree are $\delta^-(G)$ and $\Delta^-(G)$; for outdegree use $\delta^+(G)$ and $\Delta^+(G)$.
\Prop In a digraph $G$, $\sum_{v\in V(G)} d^+(v) = e(G) = \sum_{v\in V(G)} d^-(v)$.
\Prop A list of pairs of nonnegative integers is realizable as the degree pairs of a digraph if and only if the sum of the first coordinates equals the sum of the second coordinates.
\Def The {\bf split} of a digraph $D$ is a bipartite graph $G$ with partite sets $V^+$, $V^-$ are copies of $V(D)$. For each vertex $x \in V(D)$, there is one vertex $x^+ \in V^+$ and one vertex $x^- \in V^-$. For each edge from $u$ to $v$ in $D$, there is an edge with endpoints $u^+, v^-$ in $G$.
\Def An {\bf Eulerian trail} in a digraph is a trail containing all edges. An {\bf Eulerian circuit} is a closed trail containing all edges. A digraph is {\bf Eulerian} if it has an Eulerian circuit.
\Lma If $G$ is a digraph with $\delta^+(G) \geq 1$, then $G$ contains a cycle. The same conclusion holds when $\delta^-(G) \geq 1$.
\Thm A digraph is Eulerian if and only if $d^+(v) = d^-(v)$ for each vertex $v$ and the underlying graph has at most one nontrivial component.
\Def The {\bf de Bruijn graph} of order $4n$ on an alphabet of size $k$ is denoted $D_{n,k}$. Typically, $k = 2$. The vertices of $D_{n,k}$ are the $(n-1)$-tuples of $k$ elements. Put an edge from $a$ to $b$ if the last $n-2$ entries of $a$ agree with the first $n-2$ entries of $b$. Label the edge with the last entry of $b$.
\Thm The digraph $D_{n,2}$ is Eulerian, and the edge labels on the edges of any Eulerian circuit of $D_{n,2}$ form a cyclic arrangement in which the $2^n$ consecutive segments of length $n$ are distinct.
\Def An {\bf orientation} of a graph $G$ is a digraph $D$ obtained from $G$ by choosing an orientation ($x \to y$ or $y \to x$) for each edge $xy \in E(G)$. An {\bf oriented graph} is an orientation of a simple graph. A {\bf tournament} is an orientation of a complete graph.
\Def The outdegree sequence of a tournament is its {\bf score sequence}. In a digraph, a {\bf king} is a vertex from which every vertex is reachable by a path of length at most $2$.
\Prop Every tournament has a king.
{\bigbf Chapter 2: Trees and Distance}
{\bf Section 2.1: Basic Properties}
\Def A graph with now cycles is {\bf acyclic}. A {\bf forest} is an acyclic graph. A {\bf tree} is a connected acyclic graph. A {\bf leaf} (or {\bf pendant vertex}) is a vertex of degree 1. A {\bf spanning subgraph} of $G$ is a subgraph with vertex set $V(G)$. A {\bf spanning tree} is a spanning subgraph that is a tree. A {\bf star} is a tree consisting of one vertex adjacent to all the others. The $n$-vertex stare is the biclique $K_{1,n-1}$.
\Lma Every tree with at least two vertices has at least two leaves. Deleting a leaf from an $n$-vertex tree produces a tree with $n-1$ vertices.
\Thm For an $n$-vertex graph $G$ with $n \geq 1$, the following are equivalent (and characterize the trees with $n$ vertices): A. $G$ is connected and has no cycles. B. $G$ is connected and has $n-1$ edges. C. $G$ has $n-1$ edges and no cycles. D. $G$ has no loops and has, for each $u,v \in V(G)$ exactly one $u,v$-path.
\Cor A. Every edge of a tree is a cut-edge. B. Adding one edge to a tree forms exactly one cycle. C. Every connected graph contains a spanning tree.
\Prop If $T$, $T'$ are spanning trees of a connected graph $G$ and $e \in E(T) \setminus E(T')$, then there is an edge $e' \in E(T') \setminus E(T)$ such that $T - e + e'$ is a spanning tree of $G$.
\Prop If $T$, $T'$ are spanning trees of a connected graph $G$ and $e \in E(T) \setminus E(T')$, then there is an edge $e' in T(T') \setminus E(T)$ such that $T' + e - e'$ is a spanning tree of $G'$.
\Prop If $T$ is a tree with $k$ edges and $G$ is a simple graph with $\delta(G) \geq k$, then $T$ is a subgraph of $G$.
\Def If $G$ has a $u,v$-path, then the {\bf distance} from $u$ to $v$, written $d_G(u,v)$ or simply $d(u,v)$ is the least length of a $u,v$-path. If $G$ has no such path, then $d(u,v) = \infty$. The {\bf diameter} ($\diam G$) is $\displaystyle\max_{u,v \in V(G)} d(u,v)$. The {\bf eccentricity} of a vertex $u$, written $\epsilon(u)$, is $\displaystyle\max_{v\in V(G)} d(u,v)$. The {\bf radius} of a graph $G$, written $\rad G$, is $\displaystyle\min_{u \in V(G)} \epsilon(u)$.
\Thm If $G$ is a simple graph, then $\diam G \geq 3 \Rightarrow \diam \overline G \leq 3$.
\Def The {\bf center} of a graph $G$ is the subgraph induced by the vertices of minimum eccentricity.
\Thm The center of a tree is a vertex or and edge.
\Def The {\bf Wiener index} of a graph $G$, written $W(G)$ or $D(G)$, is the sum of minimum distances among pairs of vertices: $D(G) = \sum_{u,v \in V(G)} d_G(u,v)$.
\Thm Among trees with $n$ vertices, the Wiener index $D(T)$ is minimized by stars and maximized by paths, both uniquely.
\Lma If $H$ is a subgraph of $G$, then $d_G(u,v) \leq d_H(u,v)$.
\Cor If $G$ is a connected $n$-vertex graph, then $D(G) \leq D(P_n)$.
{\bf Section 2.2: Spanning Trees and Enumeration}
Alg: The following algorithm produces a {\bf Pr{\" u}fer code}:
\hspace{0.2in}{\bf Input:} A tree $T$ with vertex set $S \subseteq \N$.
\hspace{0.2in}{\bf Output:} The code $f(T) = (a_1,\dots, a_{n-2})$.
\hspace{0.2in}{\bf Iteration:} At the $i$th step, delete the least remaining leaf, and let $a_i$ be the {\it neighbor} of this leaf.
\Thm ``{\it Cayley's Formula}" For a set $S \subseteq \N$ of size $n$, there are $n^{n-2}$ trees with vertex set $S$.
\Cor Given positive integers $d_1,\dots, d_n$ summing to $2n-2$, there are exactly $\frac{(n-2)!}{\prod(d_i-1)!}$ trees with vertex set $[n]$ such that vertex $i$ has degree $d_i$, for each $i$.
\Def In a graph $G$, a {\bf contraction} of edge $e$ with endpoints $u, v$ is the replacement of $u$ and $v$ with a single vertex whose incident edges are the edges other than $e$ that were incident to $u$ or $v$. The resulting graph $G \cdot e$ has one edge less than $G$.
\Prop Let $\tau(G)$ denote the number of spanning trees of a graph $G$. If $e \in E(G)$ is not a loop, then $\tau(G) = \tau(G-e) + \tau(G \cdot e)$.
Rmk: If $G$ is a connected loopless graph with no cycle of length at least $3$, then $\tau(G)$ is the product of the edge multiplicities. A disconnected graph has no spanning trees.
\Thm ``{\it Matrix Tree Theorem}" Given a loopless graph $G$ with vertex set $v_1, \dots, v_n$, let $a_{i,j}$ be the number of edges with endpoints $v_i$ and $v_j$. Let $Q$ be the matrix in which entry $(i, j)$ is $-a_{i,j}$ when $i \neq j$ and is $d(v_i)$ when $i = j$. If $Q^*$ is a matrix obtained by deleting row $s$ and column $t$ of $Q$, then $\tau(G) = (-1)^{s+t}\det Q^*$.
Conj: If $T$ is a fixed tree with $m$ edges, then $K_{2m+1}$ decomposes into $2m+1$ copies of $T$.
\Def A {\bf graceful labeling} of a graph $G$ with $m$ edges is a function $f: V(G) \to \{0, \dots, m\}$ such that distinct vertices receive distinct numbers and $\{ |f(u)-f(v)| | uv \in E(G)\} = \{1, \dots, m\}$. A graph is {\bf graceful} if it has a graceful labeling.
Conj ({\it Graceful Tree Conjecture}): Every tree has a graceful labeling.
\Thm If a tree $T$ with $m$ edges has a graceful labeling, then $K_{2m+1}$ has a decomposition into $2m+1$ copies of $T$.
\Def A {\bf caterpillar} is a tree in which a single path (the {\bf spine}) is incident to (or contains) every edge.
\Thm A tree is a caterpillar if and only if it does not contain the $Y$ tree, formed by attaching an additional vertex adjacent to each leaf of the three-star (or claw).
Deff: A {\bf branching-} or {\bf out-tree} is an orientation of a tree having a root of indegree $0$ and all other vertices of indegree $1$. An {\bf in-tree} is an out-tree with edges reversed.
\Thm ``{\bf Directed Matrix Tree Theorem}" Given a loopless digraph $G$, let $Q^- = D^- - A'$ and $Q^+ = D^+ - A'$, where $D^-$ and $D^+$ are the diagonal matrices of indegrees and outdegrees in $G$ and the $i, j$th-entry of $A'$ is the number of edges from $v_j$ to $v_i$. The number of spanning out-trees (in-trees) of $G$ rooted at $v_i$ is the value of eacch cofactor in the $i$th row of $Q^-$ ($i$th column of $Q^+$).
\Lma In a strong digraph, every vertex is the root of an out-tree and an in-tree.
Alg ({\it Eulerian circuit in a directed graph}):
\hspace{0.2in}{\bf Input:} An Eulerian digraph $G$ without isolate vertices and a spanning in-tree $T$ consisting of paths to a vertex $v$.
\hspace{0.2in}{\bf Step 1:} For each $u \in V(G)$, specify an ordering of the edges that leave $u$, such that for $u \neq v$, the edge leaving $u$ in $T$ comes last.
\hspace{0.2in}{\bf Step 2:} Beginning at $v$, construct an Eulerian circuit by always exiting the current vertex $u$ along the next unused edge in the ordering specified at $u$.
%\Thm The previous algorithm always produces an Eulerian circuit.
\Thm In an Eulerian digraph with $d_i = d^\pm(v_i)$ the number of Eulerian circuits is $c\prod_{i}(d_i-1)!$ where $c$ counts the in-trees to or out-trees from any vertex.
{\bf Section 2.3: Optimization and Trees}
\Def A {\bf weighted graph} is a graph with numerical labels on the edges. We consider only nonnegative edge weights for now.
Alg ({\it Kruskal's Algorithm for Minimum Spanning Trees}): [Omitted by CS Major]
Alg ({\it Prim's Algorithm for Minimum Spanning Trees}): [Omitted by CS Major]
\Def The {\bf distance} $d(u,z)$ in a weighted graph is the minimum sum of the weights on the edges in a $u,z$-path.
Alg ({\it Dijkstra's Algorithm for distance from one vertex}): [Omitted by CS Major]
Alg ({\it Breadth-First Search for Unweighted Graphs}): [Omitted by CS Major]
\Def The {\bf Chinese Postman Problem} attempts to find the shortest-weight Eulerian circuit, possibly by adding multiedges to the graphs (hopefully with low weights on the edges). When there are two odd vertices, the minimal route is to duplicate the edges on the shortest path between them and find any Eulerian circuit.
\Def A {\bf rooted tree} is a tree with one vertex $r$ chosen as {\bf root}. For each vertex $v$, let $P(v)$ be the unique $v,r$-path. The {\bf parent} of $v$ is the neighbor on $P(v)$; its {\bf children} are its other neighbors. Its {\bf ancestors} are the vertices of $P(v) - v$. Its {\bf descendants} are the vertices such that $P(u)$ contains $v$. The {\bf leaves} are the vertices with no children. A {\bf rooted plane tree} or {\bf planted tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.
\Def A {\bf binary tree} is a rooted plane tree where each vertex has at most two children, and each child of a vertex is designated as its {\bf left child} or {\bf right child} . The subtrees rooted a the children of the root are the {\bf left subtree} and the {\bf right subtree}. A {\bf $k$-ary tree} allows each vertex up to $k$ children.
Alg ({\it Huffmans' Algorithm for prefix-free coding}): {\bf Idea:} Infrequent items should have longer codes; put infrequent items deeper by combining them into parent nodes.
\hspace{0.2in}{\bf Input:}Weights (frequencies or probabilities) $p_1,\dots,p_n$
\hspace{0.2in}{\bf Output:}Prefix-free code (equivalently, a binary tree).
\hspace{0.2in}{\bf Initial Case:} When $n = 2$, the optimal length is one, with $0$ and $1$ being the codes assigned to the two items (the tree has a root and two leaves; $n = 1$ can also be used as the initial case).
\hspace{0.2in}{\bf Recursion:} When $n > 2$, replace the two least likely items $p, p'$ with a single item $q$ of weight $p + p'$. Treat the smaller set as a problem with $n-1$ items. After solving it, give children with weights $p,p'$ to the resulting leaf with weight $q$. Equivalently, replace the code computed for the combined item with its extensions by $1$ and $0$ assigned to the items that were replaced.
\Thm Given a probability distribution $\{p_i\}$ on $n$ items, Huffman's Algorithm produces the prefix-free code with minimum expected length.
\Def The {\bf entropy} of a discrete probability distribution $\{p_i\}$ is $-\sum p_i \lg p_i$. *The negative sign is there since the logarithm of each $p_i$ is negative.
{\bigbf Chapter 3: Matchings and Factors}
{\bf Section 3.1: Matchings and Covers}
Def; A {\bf matching} in a graph $G$ is a set of non-loop edges with no shared endpoints. The vertices incident to the edges of a matching $M$ are {\bf saturated} by $M$; the others are {\bf unsaturated}. A {\bf perfect matching} in a graph is a matching that saturates every vertex. The {\bf size} of a matching is its number of edges.
\Def A {\bf maximal matching} in a graph is a matching that cannot be enlarged by adding an edge. A {\bf maximum matching} is a matching of maximum size among all matchings in the graph.
\Def Given a matching $M$, an $M$-{\bf alternating path} is a path that alternates between edges in $M$ and edges not in $M$. An $M$-alternating path whose endpoints are unsaturated by $M$ is an $M$-{\bf augmenting path}.
\Def If $G$ and $H$ are graphs with vertex set $V$, then the {\bf symmetric difference} $G \Delta H$ is the graph with vertex set $V$ whose edges are all those edges appearing in exactly one of $G$ and $H$. We also use this notation for sets of edges, such as in a matching.
\Lma Every component of the symmetric difference of two matchings is a path or an even cycle.
\Thm A matching $M$ in a graph $G$ is a maximum matching in $G$ if and only if $G$ has no $M$-augmenting path.
\Def The condition ``For all $S \subset X, |N(S)| \geq |S|$" is {\bf Hall's Condition}.
\Thm ``{\it Hall's Theorem}" An $X,Y$-bigraph $G$ has a matching that saturates $X$ if and only if $|N(S)| \geq |S|$ for all $S \subseteq X$.
Note: When the sets of the bipartition have the same size, Hall's Theorem is the {\it Marriage Theorem}.
\Cor For $k > 0$, every $k$-regular bipartite graph has a perfect matching.
\Def A {\bf vertex cover} of a graph $G$ is a set $Q \subseteq V(G)$ that contains at least one endpoint of every edge. The vertices in $Q$ {\bf cover} $E(G)$.
\Thm If $G$ is a bipartitie graph, then the maximum size of a matching in $G$ equals the minimum size of a vertex cover of $G$.
\Def A {\bf min-max relation} is a theorem stating equality between the answers to a minimization problem over a class of instances.
\Def The {\bf independence number} of a graph is the maximum size of an independent set of vertices, denoted $\alpha(G)$. An {\bf edge cover} of $G$ is a set $L$ of edges such that every vertex of $G$ is incident to some edge of $L$. The following table describes some notation:
\begin{center}
\begin{tabular}[h]{llcll}
maximum size of independent set & $\alpha(G)$ & & maximum size of matching & $\alpha'(G)$\\
minimum size of vertex cover & $\beta(G)$ & & minimum size of edge cover & $\beta'(G)$
\end{tabular}
\end{center}
\Lma in a graph $G$, $S \subseteq V(G)$ is an independent set if and only if $\overline{S}$ is a vertex cover, and hence $\alpha(G) + \beta(G) = n(G)$.
\Thm If $G$ is a graph without isolated vertices, then $\alpha'(G) + \beta'(G) = n(G)$.
\Cor If $G$ is a bipartite graph with no isolated vertices, then $\alpha(G) = \beta'(G)$.
\Def In a graph $G$, a set $S \subseteq V(G)$ is a {\bf dominating set} if every vertex not in $S$ has a neighbor in $S$. The {\bf domination number} $\gamma(G)$ is the minimum size of a dominating set in $G$.
\Def The {\bf closed neighborhood} $N[v]$ of a vertex$v$ in a graph is $N(v) \cup \{ v\}$, the set of vertices {\it dominated by} $v$.
\Thm Every $n$-vertex graph with minimum degree $k$ has a dominating set of size at most $n \frac{1+\ln(k+1)}{k+1}$.
\Def A dominating set $S$ in $G$ is:
\hspace{.2in}a {\bf connected dominating set} if $G[S]$ is connected.
\hspace{.2in}an {\bf independent dominating set} if $G[S]$ is independent, and
\hspace{.2in}a {\bf total dominating set} if $G[S]$ has no isolated vertex.
\Lma A set of vertices in a graph is an independent dominating set if and only if it is a maximal independent set.
\Thm Every claw-free graph has an independent dominating set of size $\gamma(G)$.
{\bf Section 3.3: Matchings in General Graphs}
\Def A {\bf factor} of a graph $G$ is a spanning subgraph of $G$. A {\bf $k$-factor} is a spanning $k$-regular subgraph. An {\bf odd component} of a graph is a component of odd order; the number of odd components of $H$ is $o(H)$.
\Def The condition ``For all $S \subseteq V(G), o(G-S) \leq |S|$" is {\bf Tutte's Condition}.
\Thm ``{\it Tutte's 1-Factor Theorem}" A graph $G$ has a $1$-factor if and only if $o(G-S) \leq |S|$ for every $S \subseteq V(G)$.
% FIX THE v to be OR V
\Def The {\bf join} of simple graphs $G$ and $H$, written $G \operatorname{v} H$ is the graph obtained from the disjoint union $G+H$ by adding the edges $\{xy | x\in V(G), y\in V(H)\}$.
\Cor The largest number of vertices saturated by a matching in $G$ is $\min_{S\subseteq V(G)} \{n(G) - d(S)\}$ where $d(S) = o(G-S) - |S|$.
\Cor Every $3$-regular graph with no cut-edge has a $1$-factor.
\Cor Every regular graph with positive even degree has a $2$-factor.
\end{document}