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.

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. |

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}
```

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}
```

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}
```

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.

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