home

# Graphs

Graphs are discrete structures consisting of vertices and edges.

Formally a graph is defined as $G = (V,E)$ where $$V$$ is a set of nodes, or vertices and $$E$$ is a set of edges connecting these.

## Terms

term description
adjacent Vertices that share an edge, or edges that share a vertex.
incident If a vertex $$v$$ is and endpoints of an edge $$e$$, then $$e$$ and $$v$$ are incident.
walk Sequence of vertices and edges that can include repeat elements.
trial A walk in which no edge is repeated (vertices may repeat).
circuit A closed trail - starts and ends at the same vertex.
path A trail in which neither vertices nor edges are repeated.
Eulerian path A path that uses each edge once.
Hamiltonian path A path that visits each vertex exactly once.
degree The number of edges incident to a vertex.
degree sequence A decreasing list of vertex degrees that form a graph. Always even when summed.
isomorphism Two graphs with a common structure. See Isomorphic Graphs.

## Special graphs

### Simple graph

No loops, no parallel edges.

For any simple graph $$G$$ with $$n$$ vertices, the degree of each vertex is at most $$n-1$$.

\begin{document}

\tikzset{unode/.style = {
circle,
draw=cyan!50!black,
thick,
fill=cyan!50!black,
inner sep=2.3pt,
minimum size=2.3pt } }
\tikzset{uedge/.style = {
draw=cyan!70!black,
very thick} }

\begin{tikzpicture}

\node[unode] (1) at (0,0) {};
\node[unode] (2) at (1,0) {};
\node[unode] (3) at (1,1) {};
\node[unode] (4) at (0,1) {};
\path[uedge] (1) edge (4) edge (3) edge (2);

\end{tikzpicture}
\end{document}

### Regular graph

A graph is regular if all local degrees are equivalent.

A graph $$G$$ where all the vertices are degree $$r$$ is stated to be $$r$$-regular.

As the degree sequence of an r-regular graph is $$r,r,r,\dots,r$$ ($$n$$ times), the sum of the degree sequence is $$r \times n$$, and the number of edges is $$\frac{r \times n}{2}$$.

\begin{document}

\tikzset{unode/.style = {
circle,
draw=cyan!50!black,
thick,
fill=cyan!50!black,
inner sep=2.3pt,
minimum size=2.3pt } }
\tikzset{uedge/.style = {
draw=cyan!70!black,
very thick} }

\begin{tikzpicture}

\node[unode] (1) at (0,0) {};
\node[unode] (2) at (1,0) {};
\node[unode] (3) at (1,1) {};
\node[unode] (4) at (0,1) {};
\path[uedge] (1) edge (2) edge (3);
\path[uedge] (4) edge (2) edge (3);

\end{tikzpicture}
\end{document}

### Complete graph

A complete graph is a simple graph where every pair of vertices are adjacent.

A complete graph with $$n$$ vertices is represented as $$K_n$$.

Every vertex has degree $$n-1$$. Sum of degree sequence is $$n(n-1)$$. Number of edges is $$\frac{n(n-1)}{2}$$.

\begin{document}

\tikzset{unode/.style = {
circle,
draw=cyan!50!black,
thick,
fill=cyan!50!black,
inner sep=2.3pt,
minimum size=2.3pt } }
\tikzset{uedge/.style = {
draw=cyan!70!black,
very thick} }

\begin{tikzpicture}

\node[unode] (1) at (0,0) {};
\node[unode] (2) at (1,0) {};
\node[unode] (3) at (1,1) {};
\node[unode] (4) at (0,1) {};
\path[uedge] (1) edge (2) edge (3) edge (4);
\path[uedge] (3) edge (2) edge (4) edge (1);
\path[uedge] (4) edge (2);

\end{tikzpicture}
\end{document}

### Bipartite Graph

A bipartite graph has a set of vertices $$V$$ that can be partitions into two non-empty disjoint sets $$V_1$$ and $$V_2$$ such that each edge has one endpoint in each partition.

\begin{document}

\tikzset{unode/.style = {
circle,
draw=cyan!50!black,
thick,
fill=cyan!50!black,
inner sep=2.3pt,
minimum size=2.3pt } }
\tikzset{uedge/.style = {
draw=cyan!70!black,
very thick} }

\begin{tikzpicture}

\node[unode] (1) at (0,0) {};
\node[unode] (2) at (0,1) {};
\node[unode] (3) at (0,2) {};

\node[unode] (a) at (1,0.5) {};
\node[unode] (b) at (1,1.5) {};

\path[uedge] (b) -- (1) -- (a) -- (2) -- (b) -- (3) -- (a);

\end{tikzpicture}
\end{document}

Always 2-colourable. No odd-length cycles.

### Forest

A forest is a disconnected graph containing no cycles. More simply, many Trees.