## Graph Theory

Graph Theory is a way to model a collection of objects, and the connections between those objects.

$$\text{A graph }G\text{ is a set }V\text{ of vertices together with a set }E\text{ of edges which }\\\text{are unordered pairs of distinct vertices.}$$

• Vertices are points in the graph.

• Edges are unordered pairs of distinct vertices.

• A simple graph is one with no multiple edges.

• A loop is an edge from a vertex to itself.

• Vertices have to be unique.

• Edges do not have to be straight lines.

• A vertex $v$ is adjacent to vertex $q$ if there is edge $\{v,q\}$ in the graph.

The complete graph on $n$ vertices, $K_n$, is defined by taking a set of $n$ vertices and connecting every pair of distinct vertices by an edge.

• The total number of edges in $K_n$ is $\frac{n(n-1)}2$.

Complete graphs.

The Complete Bipartite Graph $K_{m,n}$ is defined by splitting the vertices into $2$ subsets, one of size $m$ and one of size $n$, and joining all vertices in one subset to all vertices in the other.

• The total number of edges in $K_{m,n}$ is $m\cdot n$.

Complete bipartite graphs.

The Cycle Graph on $n\geq3$ vertices $\text{C}_n$ is defined by the following: