\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{madsysharma}
\pdfinfo{
  /Title (graph-theory-and-trees.pdf)
  /Creator (Cheatography)
  /Author (madsysharma)
  /Subject (Graph Theory and Trees Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Graph Theory and Trees Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{madsysharma} via \textcolor{DarkBackground}{\uline{cheatography.com/208834/cs/45221/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}madsysharma \\
  \uline{cheatography.com/madsysharma} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 9th December, 2024.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Basic Graph Terms}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{GRAPH:}} \newline % Row Count 1 (+ 1)
\{\{fa-chevron-right\}\}A simple graph G consists of {\bf{a non-empty finite set V of elements called vertices/nodes}} and a {\bf{finite set E of distinct unordered pairs of distinct elements of V called edges}}. V and E are called the {\bf{vertex set and edge set respectively}}. G is written as a two-tuple {\bf{G=(V,E)}} \newline % Row Count 8 (+ 7)
\{\{fa-chevron-right\}\}If the edges don't have a direction (indicated with an arrow), graph G is an {\bf{undirected graph}}. Else, it is a {\bf{directed graph or digraph}} \newline % Row Count 12 (+ 4)
\{\{fa-chevron-right\}\}If G has multiple edges between a pair of nodes, it is called a {\bf{multigraph if it is undirected or a multidigraph if it is directed}} \newline % Row Count 16 (+ 4)
{\bf{DEFINITIONS FOR UNDIRECTED GRAPHS:}} \newline % Row Count 17 (+ 1)
\{\{fa-chevron-right\}\}In an undirected graph, a {\bf{proper edge joins one vertex to another}} and a {\bf{self loop joins a vertex to itself}}. \newline % Row Count 20 (+ 3)
\{\{fa-chevron-right\}\}{\bf{|V| is called the order of the graph}} and {\bf{|E| is called the size of the graph}}. G is {\bf{finite if both order and size are finite}}, else it is {\bf{infinite}} \newline % Row Count 24 (+ 4)
\{\{fa-chevron-right\}\}Edge e \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E (represented by vertex pair (u,v) where u,v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V ) in an undirected graph can also be represented by (v,u). \newline % Row Count 27 (+ 3)
\{\{fa-chevron-right\}\}Vertices u and v are {\bf{adjacent to each other if there's an edge e = (u,v) \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E}}. e is then {\bf{incident upon u and v}}, and u and v are also called {\bf{neighbors of each other}} \newline % Row Count 31 (+ 4)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Basic Graph Terms (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}Degree of vertex v in an undirected graph is given by {\bf{deg(v) = \# of proper edges + 2 * \# of self-loops}} \newline % Row Count 3 (+ 3)
\{\{fa-chevron-right\}\}A {\bf{multiedge is a set of multiple edges between the same vertex pair}}. \newline % Row Count 5 (+ 2)
\{\{fa-chevron-right\}\}A {\bf{loopless graph}} is a {\bf{graph without self-loops}}. A graph {\bf{without self-loops and multiedges}} is called a {\bf{simple graph}} \newline % Row Count 9 (+ 4)
{\bf{DEFINITIONS FOR DIRECTED GRAPHS OR DIGRAPHS:}} \newline % Row Count 10 (+ 1)
\{\{fa-chevron-right\}\}A directed edge is called an {\bf{arc}} \newline % Row Count 12 (+ 2)
\{\{fa-chevron-right\}\}If an arc {\bf{starts at vertex u and ends at vertex v}} , then {\bf{u and v are called the head and tail of the arc respectively}}. Vertex v is the {\bf{successor of vertex u}}, and vertex u is the {\bf{predecessor of vertex v.}} \newline % Row Count 17 (+ 5)
\{\{fa-chevron-right\}\}The {\bf{set of arcs which end at vertex v}} are called {\bf{in-edges or in-arcs}}. Similarly, the {\bf{set of arcs which start from vertex v}} are called {\bf{out-edges or out-arcs}}. \newline % Row Count 21 (+ 4)
\{\{fa-chevron-right\}\}The {\bf{out-degree of a vertex}} is {\bf{the number of edges starting from it}}. Similarly, the {\bf{in-degree of a vertex}} is the {\bf{number of edges ending at it}}. Each {\bf{self-loop at vertex v}} contributes {\bf{a count of 1 to both the in-degree and out-degree}}. The {\bf{degree of a vertex in a digraph}} is given by {\bf{deg(v) = in-degree of v + out-degree of v}} \newline % Row Count 29 (+ 8)
\{\{fa-chevron-right\}\} A directed graph is {\bf{strongly connected if there's a path from a to b,  \textasciitilde{}\textasciitilde{}V\textasciitilde{}\textasciitilde{} a, b \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V}} \newline % Row Count 32 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Basic Graph Terms (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\} A directed graph is {\bf{weakly connected if there's a path between every two vertices in the underlying undirected graph}}% Row Count 3 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Planar and Bipartite Graphs}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}Graph G is {\bf{planar}} if it {\bf{can be drawn in the plane with edges intersecting ONLY at vertices of G}}. \newline % Row Count 3 (+ 3)
\{\{fa-chevron-right\}\}Such a drawing is called {\bf{embedding of G in the plane}}. \newline % Row Count 5 (+ 2)
\{\{fa-chevron-right\}\}Graph G is {\bf{bipartite if V = V\textasciitilde{}1\textasciitilde{} U V\textasciitilde{}2\textasciitilde{} with V' = V\textasciitilde{}1\textasciitilde{} . V\textasciitilde{}2\textasciitilde{} = null set and every edge of G takes the form (a,b) with a \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V\textasciitilde{}1\textasciitilde{} and b \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V\textasciitilde{}2\textasciitilde{}}} \newline % Row Count 9 (+ 4)
\{\{fa-chevron-right\}\}If {\bf{each vertex in V\textasciitilde{}1\textasciitilde{} is joined with every vertex in V\textasciitilde{}2\textasciitilde{}, then we get a complete bipartite graph, denoted by K\textasciitilde{}m,n\textasciitilde{} where |V\textasciitilde{}1\textasciitilde{}| = m and |V\textasciitilde{}2\textasciitilde{}|=n}} \newline % Row Count 13 (+ 4)
\{\{fa-chevron-right\}\}If {\bf{G=(V,E) is a loop-free, undirected graph and E != null set}}, an {\bf{elementary subdivision of G results when edge e = (u,w) is removed from G and then edges (u,v) and (v,w) are added to G - e, where v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V}} \newline % Row Count 18 (+ 5)
\{\{fa-chevron-right\}\}{\bf{Loop free, undirected graphs G\textasciitilde{}1\textasciitilde{} = (V\textasciitilde{}1\textasciitilde{}, E\textasciitilde{}1\textasciitilde{}) and G\textasciitilde{}2\textasciitilde{} = (V\textasciitilde{}2\textasciitilde{}, E\textasciitilde{}2\textasciitilde{})}} are called {\bf{homeomorphic if they are isomorphic OR they both can be obtained from the same loop free, undirected graph H by a sequence of elementary subdivisions.}} \newline % Row Count 24 (+ 6)
\{\{fa-chevron-right\}\}{\bf{Kuratowski's Theorem: Graph G is nonplanar iff it contains a subgraph homeomorphic to either K\textasciitilde{}5\textasciitilde{} or K\textasciitilde{}3,3\textasciitilde{}}} \newline % Row Count 27 (+ 3)
\{\{fa-chevron-right\}\}{\bf{Euler's theorem: Let G=(V,E) be a connected planar graph or multigraph, with |V| = v and |E| = e. If r is the \# of regions in the plane determined by a planar embedding/depiction of G, and one of these regions (called the infinite region) has infinite area, then v - e + r =2}} \newline % Row Count 33 (+ 6)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Planar and Bipartite Graphs (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{For each region R in a planar embedding of a (planar) graph or multigraph, the degree of R, denoted deg (R), is the \# of edges traversed in a (shortest) closed walk about (the edges in) the boundary of R.}} \newline % Row Count 5 (+ 5)
\{\{fa-chevron-right\}\}{\bf{Corollary: Let G = (V;E) be a connected planar graph or multigraph with |V| = v and |E| = e \textgreater{} 2, and r regions. Then 3r \textless{}= 2e and e \textless{}=(3v - 6)}}% Row Count 9 (+ 4)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Subgraphs, Complements and Graph Isomorphism}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}The {\bf{subgraph G\textasciitilde{}s\textasciitilde{} of graph G=(V,E) is given by G\textasciitilde{}s\textasciitilde{} = (V\textasciitilde{}s\textasciitilde{}, E\textasciitilde{}s\textasciitilde{}) where \textasciitilde{}\textasciitilde{}O\textasciitilde{}\textasciitilde{} (null set) != V\textasciitilde{}s\textasciitilde{} , and V\textasciitilde{}s\textasciitilde{} and E\textasciitilde{}s\textasciitilde{} are subsets of V and E respectively}} \newline % Row Count 4 (+ 4)
\{\{fa-chevron-right\}\}NOTE: {\bf{if (u,v) \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E\textasciitilde{}s\textasciitilde{}, then u,v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V\textasciitilde{}s\textasciitilde{}}} \newline % Row Count 6 (+ 2)
\{\{fa-chevron-right\}\}A {\bf{spanning subgraph of G, where G can be directed or undirected}} is a {\bf{subgraph composed of all vertices of G}}, ie: {\bf{V\textasciitilde{}s\textasciitilde{} = V}} \newline % Row Count 10 (+ 4)
\{\{fa-chevron-right\}\}If {\bf{G = (V,E) is a directed/undirected graph, and if U is not a null set and is a subset of V,}} then the {\bf{induced subgraph on U is a graph whose vertex set is U, and whose edge set contains every edge in E having endpoints in U}}. \newline % Row Count 16 (+ 6)
\{\{fa-chevron-right\}\}{\bf{Deleting an edge e in graph G (which can be directed/undirected) creates a subgraph denoted by G - e , which contains all vertices of G and all edges except e}}. \newline % Row Count 20 (+ 4)
\{\{fa-chevron-right\}\}{\bf{Deleting a vertex v in graph G(which can be directed/undirected) creates a subgraph denoted by G - v, which contains all vertices of G except for v, and all edges in G except those incident on vertex v}} \newline % Row Count 25 (+ 5)
\{\{fa-chevron-right\}\}If {\bf{V is a set of n vertices}}, then the {\bf{complete graph on V, denoted by K\textasciitilde{}n\textasciitilde{}, is a loop-free, undirected graph where \textasciitilde{}\textasciitilde{}V\textasciitilde{}\textasciitilde{} a, b \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V AND a != b, there exists edge (a,b)}} \newline % Row Count 29 (+ 4)
\{\{fa-chevron-right\}\}If {\bf{G is a loopless, undirected graph with n vertices}}, then the {\bf{complement of G (denoted by G with a bar on top) is the subgraph of K\textasciitilde{}n\textasciitilde{} containing all vertices in G and all edges not in G}} \newline % Row Count 34 (+ 5)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Subgraphs, Complements and Graph Isomorphism (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}If {\bf{G = K\textasciitilde{}n\textasciitilde{}}}, then {\bf{its complement has all the n vertices and no edges}}. Such a graph is called {\bf{null graph}}. \newline % Row Count 3 (+ 3)
\{\{fa-chevron-right\}\}For {\bf{two undirected graphs G\textasciitilde{}1\textasciitilde{} = (V\textasciitilde{}1\textasciitilde{}, E\textasciitilde{}1\textasciitilde{}) and G\textasciitilde{}2\textasciitilde{} = (V\textasciitilde{}2\textasciitilde{}, E\textasciitilde{}2\textasciitilde{})}}, a {\bf{function f: V\textasciitilde{}1\textasciitilde{} -\textgreater{} V\textasciitilde{}2\textasciitilde{} is called graph isomorphism}} if {\bf{a) f is one-to-one and onto}} and {\bf{b) \textasciitilde{}\textasciitilde{}V\textasciitilde{}\textasciitilde{} a,b \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V\textasciitilde{}1\textasciitilde{}, (a,b) \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E\textasciitilde{}1\textasciitilde{} iff (f(a), f(b)) \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E\textasciitilde{}2\textasciitilde{}}}. The two graphs are called {\bf{isomorphic graphs}} if such a function exists.% Row Count 10 (+ 7)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Walks, Paths and Circuits}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}A {\bf{walk in graph G}} is a {\bf{sequence of nodes v\textasciitilde{}1\textasciitilde{}, v\textasciitilde{}2\textasciitilde{}, ... , v\textasciitilde{}n\textasciitilde{} where n\textgreater{}=2 and (v\textasciitilde{}i\textasciitilde{}, v\textasciitilde{}i+1\textasciitilde{}) \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} E for i = 1, 2, ... , n-1.}} \newline % Row Count 4 (+ 4)
\{\{fa-chevron-right\}\}{\bf{Repetition of vertices and edges in a walk is permitted}} \newline % Row Count 6 (+ 2)
\{\{fa-chevron-right\}\}{\bf{If G isn't weighted, then the length of the walk is n-1. Else, the length is the sum of the weights of all edges in the walk (provided the weights are non-negative)}} \newline % Row Count 10 (+ 4)
\{\{fa-chevron-right\}\}A {\bf{trail}} is a {\bf{type of walk in which all edges are different}}. {\bf{Repetition of vertices is permitted while repetition of edges are not.}} \newline % Row Count 14 (+ 4)
\{\{fa-chevron-right\}\}A {\bf{path}} is a {\bf{trail in which all the vertices are different (except the starting and ending vertices may be the same)}}. There is {\bf{no repetition of edges and vertices}}. \newline % Row Count 18 (+ 4)
\{\{fa-chevron-right\}\}If the {\bf{starting vertex is the same as the ending vertex}}, the walk, trail or path is {\bf{open, else it is closed.}} \newline % Row Count 21 (+ 3)
\{\{fa-chevron-right\}\}G is {\bf{connected if each vertex pair is joined by a path, else it is disconnected}} \newline % Row Count 24 (+ 3)
\{\{fa-chevron-right\}\}Vertex v is {\bf{reachable}} from vertex u {\bf{if there's a path connecting the two.}} \newline % Row Count 27 (+ 3)
\{\{fa-chevron-right\}\}A {\bf{circuit or cycle}} is a {\bf{walk with the same starting and ending vertices, with no repeating vertices in between.}} \newline % Row Count 30 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Walks, Paths and Circuits (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{Hamiltonian Path}}: a {\bf{path containing all of G's vertices}} \newline % Row Count 2 (+ 2)
\{\{fa-chevron-right\}\}{\bf{Hamiltonian Cycle}}: a {\bf{cycle containing all of G's vertices}} \newline % Row Count 4 (+ 2)
{\bf{THEOREMS FOR HAMILTON CYCLES AND PATHS:}} \newline % Row Count 5 (+ 1)
\{\{fa-chevron-right\}\}Theorem: Let G = (V,E) be a loop-free undirected graph, where |V| = n \textgreater{}= 2. If deg (x) + deg (y) \textgreater{}= n - 1 for all x, y \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V , x != y, then G has a Hamilton path. \newline % Row Count 9 (+ 4)
\{\{fa-chevron-right\}\}Corollary: Let G = (V,E) be a loop-free undirected graph, where |V| = n \textgreater{}= 2. If deg (v) \textgreater{}= (n - 1)/2 for all v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V , then G has a Hamilton path. \newline % Row Count 13 (+ 4)
\{\{fa-chevron-right\}\}Ore's theorem: Let G = (V,E) be a loop-free undirected graph, where |V| = n \textgreater{}= 3. If deg (x) + deg (y) \textgreater{}= n for all nonadjacent x, y \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V , then G contains a Hamilton cycle. \newline % Row Count 17 (+ 4)
\{\{fa-chevron-right\}\}Corollary, ie: Dirac's theorem: Let G = (V,E) be a loop-free undirected graph, where |V|= n \textgreater{}= 3. If deg (v) \textgreater{}= n/2 for all v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V , then G contains a Hamilton cycle. \newline % Row Count 21 (+ 4)
\{\{fa-chevron-right\}\}Theorem: Every simple graph G = (V,E) with |V| = n \textgreater{}= 3 and at least (n\textasciicircum{}2\textasciicircum{} - 3n + 6)/2 edges has a Hamilton cycle.% Row Count 24 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Graph Representation}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{Adjacency Matrix}}: It is an {\bf{n x n matrix}} where {\bf{n = |V|}} \newline % Row Count 2 (+ 2)
\{\{fa-chevron-right\}\}Entry {\bf{A\textasciitilde{}i,j\textasciitilde{} in adjacency matrix A for an undirected graph G, where 1\textless{}=i,j\textless{}=n}} is equal to {\bf{the \# of edges between vertices v\textasciitilde{}i\textasciitilde{} and v\textasciitilde{}j\textasciitilde{} if i=j}} OR {\bf{2 * \# of self loops if i != j}} \newline % Row Count 7 (+ 5)
\{\{fa-chevron-right\}\}The {\bf{row-sum or column-sum in adjacency matrix A}} is {\bf{equal to the degree of the corresponding vertex}} \newline % Row Count 10 (+ 3)
\{\{fa-chevron-right\}\}If {\bf{G is directed}}, then {\bf{A\textasciitilde{}i,j\textasciitilde{} = \# of arcs from v\textasciitilde{}i\textasciitilde{} to v\textasciitilde{}j\textasciitilde{}}} \newline % Row Count 12 (+ 2)
\{\{fa-chevron-right\}\}The {\bf{row sum in adjacency matrix A for a digraph is equal to out-degree of the corresponding vertex}} and the {\bf{column sum is equal to the in-degree}}% Row Count 16 (+ 4)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Euler Trails and Circuits}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{Theorem}}: Let {\bf{G = (V,E) be an undirected graph or multigraph.}} Then {\bf{Sum over v\textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{}V (deg(v)) = 2 * |E|}} \newline % Row Count 3 (+ 3)
\{\{fa-chevron-right\}\}{\bf{Corollary: For any undirected graph or multigraph, the \# of vertices with odd degree must be even.}} \newline % Row Count 6 (+ 3)
\{\{fa-chevron-right\}\}{\bf{If G = (V,E) is an undirected graph/multigraph, with at least 2 vertices and no vertices are isolated}}, then: \newline % Row Count 9 (+ 3)
\{\{fa-circle\}\} {\bf{G has a Euler circuit if there's a circuit in G traversing every edge of the graph exactly once}} \newline % Row Count 12 (+ 3)
\{\{fa-circle\}\}{\bf{If there's an open trail from a to b in G, and the trail traverses each edge in G exactly once, then the trail is called a Euler trail.}} \newline % Row Count 16 (+ 4)
\{\{fa-chevron-right\}\}{\bf{Theorem:}} Let {\bf{G = (V,E) be an undirected graph/multigraph with at least 2 vertices and no vertices are isolated.}} Then {\bf{G has an Euler circuit iff every vertex in G has an even degree}}. \newline % Row Count 21 (+ 5)
\{\{fa-chevron-right\}\}{\bf{Corollary:}} If {\bf{G=(V,E) is an undirected graph/multigraph with at least 2 vertices and no isolated vertices, we can construct an Euler trail iff G is connected and has EXACTLY 2 vertices of odd degree}}. \newline % Row Count 26 (+ 5)
\{\{fa-chevron-right\}\}{\bf{Theorem:}} Let {\bf{G = (V,E) be an directed graph/multidigraph with at least 2 vertices and no vertices are isolated.}} Then {\bf{G has a directed Euler circuit iff out-degree of v = in-degree of v,  \textasciitilde{}\textasciitilde{}V\textasciitilde{}\textasciitilde{} v \textasciitilde{}\textasciitilde{}C\textasciitilde{}\textasciitilde{} V}}. \newline % Row Count 31 (+ 5)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Euler Trails and Circuits (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}An {\bf{undirected graph/multigraph where each vertex has the same degree is called a regular graph.}}. A {\bf{k-regular graph is an undirected graph/multigraph in which all vertices have the same degree k}}.% Row Count 5 (+ 5)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Trees}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{Tree: a connected graph without any cycle}} \newline % Row Count 2 (+ 2)
\{\{fa-chevron-right\}\}{\bf{TREE OBSERVATIONS:}} \newline % Row Count 3 (+ 1)
\{\{fa-circle\}\}If the {\bf{removal of an edge from connected graph G}} makes it {\bf{disconnected}}, then {\bf{G is a tree}} \newline % Row Count 6 (+ 3)
\{\{fa-circle\}\}There's {\bf{a unique path between every vertex pair in a tree}} \newline % Row Count 8 (+ 2)
\{\{fa-circle\}\}{\bf{If |V|\textgreater{}2 adding a new edge creates a cycle in a tree}} \newline % Row Count 10 (+ 2)
\{\{fa-circle\}\}{\bf{In a tree, |E| = |V| - 1}} \newline % Row Count 11 (+ 1)
\{\{fa-circle\}\}{\bf{Trees are bipartite}} \newline % Row Count 12 (+ 1)
\{\{fa-circle\}\}{\bf{Every tree can be colored using 2 colors}} \newline % Row Count 14 (+ 2)
\{\{fa-chevron-right\}\}An ensemble of trees is called a {\bf{forest}} \newline % Row Count 16 (+ 2)
\{\{fa-chevron-right\}\}A tree T=(V',E') is a {\bf{spanning tree of graph G=(V,E) if V'=V and E' is a subset of E}} \newline % Row Count 19 (+ 3)
\{\{fa-chevron-right\}\}If |V|=n,  then there are {\bf{n\textasciicircum{}(n-2)\textasciicircum{} spanning trees on V for complete graph K\textasciitilde{}n\textasciitilde{}}}.  \newline % Row Count 22 (+ 3)
\{\{fa-chevron-right\}\}{\bf{If K\textasciitilde{}m,n\textasciitilde{} is a complete bipartite graph, then the total \# of spanning trees is m\textasciicircum{}(n-1)\textasciicircum{} * n\textasciicircum{}(m-1)\textasciicircum{} }}.  \newline % Row Count 25 (+ 3)
\{\{fa-chevron-right\}\}{\bf{TYPES OF TREES:}} \newline % Row Count 26 (+ 1)
\{\{fa-circle\}\}{\bf{Path graph/linear graph:}} Has n vertices in a line, where vertices i and i+1 are connected by an edge, where i = 1,2,...,n \newline % Row Count 29 (+ 3)
\{\{fa-circle\}\}{\bf{Star tree:}} Has n\textgreater{}=2 vertices (where just one vertex is the internal vertex), and n-1 leaves.  \newline % Row Count 32 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Trees (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}{\bf{ROOTED TREE:}} \newline % Row Count 1 (+ 1)
\{\{fa-circle\}\} Has one node specified as the {\bf{root node}} \newline % Row Count 3 (+ 2)
\{\{fa-circle\}\} All other nodes in the tree are the {\bf{descendants of the root node}} \newline % Row Count 5 (+ 2)
\{\{fa-circle\}\}Each edge of this tree divides the set of vertices which are attached to either side of this edge into two groups. The {\bf{set of nodes away from the root node are called the descendant set of nodes}} with respect to this edge. Similarly, the {\bf{set of nodes towards the root node are called the ancestral set of nodes with respect to this edge}}. \newline % Row Count 13 (+ 8)
\{\{fa-circle\}\} {\bf{Child of vertex v}} is a vertex {\bf{whose immediate ancestor is v}}. A {\bf{vertex with children is called an internal vertex}}. \newline % Row Count 16 (+ 3)
\{\{fa-circle\}\} {\bf{Depth of a vertex}}: \# of edges in the unique path from the root to the vertex. \newline % Row Count 18 (+ 2)
\{\{fa-circle\}\} {\bf{Ordered tree}}: Rooted tree where {\bf{children or branches of every internal vertex are linearly ordered}}. ie: if the vertex has k children, then there is a 1st child, 2nd child and so on, all the way up to the kth child. \newline % Row Count 23 (+ 5)
\{\{fa-circle\}\}{\bf{Binary tree}}: An ordered, rooted tree where {\bf{each internal vertex has at most 2 children}} \newline % Row Count 26 (+ 3)
\{\{fa-circle\}\}{\bf{m-ary tree:}} An ordered, rooted tree where {\bf{each internal vertex has at most m children, with m = 2,3,...}} \newline % Row Count 29 (+ 3)
\{\{fa-circle\}\}{\bf{Subtree:}} A tree {\bf{rooted at a specific node which contains all its descendant nodes and the corresponding connecting edges.}} \newline % Row Count 32 (+ 3)
} \tn 
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Trees (cont)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-circle\}\}{\bf{Height of a rooted tree: Maximum \# of edges in the unique path from root to any vertex.}} \newline % Row Count 3 (+ 3)
\{\{fa-circle\}\}{\bf{Balanced tree:}} It's an {\bf{m-ary tree of height b}} where {\bf{all leaves have height b or b-1, where b=2,3,...}} \newline % Row Count 6 (+ 3)
\{\{fa-circle\}\}{\bf{d-regular tree: Each internal vertex has exactly d children}}. In a {\bf{complete d-regular tree, all leaves have the same depth}} \newline % Row Count 9 (+ 3)
\{\{fa-chevron-right\}\}{\bf{MATRIX TREE THEOREM:}} \newline % Row Count 10 (+ 1)
\{\{fa-circle\}\} Let A be the adjacency matrix of graph G.  \newline % Row Count 12 (+ 2)
\{\{fa-circle\}\} Obtain matrix D, where the diagonal elements are the sums of the columns of A and the rest of the elements are 0 \newline % Row Count 15 (+ 3)
\{\{fa-circle\}\} Obtain matrix M where M = D - A. \newline % Row Count 16 (+ 1)
\{\{fa-circle\}\} Find an (i,j) cofactor of M, determined by: (-1)\textasciicircum{}(i+j)\textasciicircum{} * determinant (M'), where M' = resulting matrix on removing row i and column j from M. {\bf{This cofactor gives the number of spanning trees for graph G.}} \newline % Row Count 21 (+ 5)
\{\{fa-circle\}\} Suppose adjacency matrix A was represented with the edge names (in lowercase letters) in place of 1's for connected edges, and 0's for non-connected edges. D would then have its diagonal entries be the sums of the columns, and 0's for the remaining elements. {\bf{If we take the (i,j) cofactor of matrix M, where M = D - A, then the result gives all possible configurations for spanning trees of graph G}}% Row Count 30 (+ 9)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Minimum Spanning Trees (MST)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{\{\{fa-chevron-right\}\}For a {\bf{weighted graph G}}, the {\bf{minimum spanning tree is a spanning tree with the smallest possible sum of edge weights}} \newline % Row Count 3 (+ 3)
\{\{fa-chevron-right\}\}For a weighted graph G, {\bf{MSTs are not unique}} \newline % Row Count 5 (+ 2)
\{\{fa-chevron-right\}\}Algorithms to determine the MST of a graph G are {\bf{greedy algorithms}} \newline % Row Count 7 (+ 2)
\{\{fa-chevron-right\}\}{\bf{PRIM'S ALGORITHM:}} \newline % Row Count 8 (+ 1)
\{\{fa-circle\}\}Pick a random vertex as the starting vertex of the MST \newline % Row Count 10 (+ 2)
\{\{fa-circle\}\}Follow steps 3 to 5 till there are vertices not included in the MST (called fringe vertices) \newline % Row Count 13 (+ 3)
\{\{fa-circle\}\}Find edges connecting any tree vertex with the fringe vertices \newline % Row Count 15 (+ 2)
\{\{fa-circle\}\}Find the minimum along these edges \newline % Row Count 16 (+ 1)
\{\{fa-circle\}\}Add the chosen edge to the MST as long as it doesn't form a cycle \newline % Row Count 18 (+ 2)
\{\{fa-circle\}\}By the end, you'll obtain the MST \newline % Row Count 19 (+ 1)
\{\{fa-chevron-right\}\}{\bf{KRUSKAL'S ALGORITHM:}} \newline % Row Count 20 (+ 1)
\{\{fa-circle\}\} Sort edges in increasing order of weight \newline % Row Count 22 (+ 2)
\{\{fa-circle\}\} Pick the first edge in the sorted order \newline % Row Count 24 (+ 2)
\{\{fa-circle\}\} Iterate through the sorted order from the second edge onwards till the end, and see if you can add that edge without creating a cycle \newline % Row Count 27 (+ 3)
\{\{fa-circle\}\} By the end, the MST will be obtained.% Row Count 29 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}