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.