A graph is specified by a set $V$ of **vertices** and a collection $E$ of unordered pair of vertices called **edges** and denoted by $G = (V, E)$. Several problems can be formulated in terms of graphs, in physics, electrical engineering and computer science. There is an entire branch devoted to the study of graph theoretic algorithms. Sometimes, graphs make problems easier to visualize (although not necessarily easier to solve, since graphs have their own complexities). We begin with some definitions:

The **order** of a graph is the number of its vertices, and the **size** is the number of edges. We concern ourselves here with directed and undirected graphs. Suppose $i, j \in V$ and that there is an edge connecting vertex $i$ to vertex $j$. If $G = (V, E)$ is a **directed graph** or **digraph** then, $(i, j) \in E$ but $(j, i) \notin E$ (or vice versa), that is, in a digraph there is a sense of direction of an edge. Therefore, we can also define the **indegree** and **outdegree** of a vertex in a digraph as the number of edges entering that vertex and the number of edges leaving that vertex, respectively. In an undirected graph all that matters is whether there is an edge connecting two vertices.

Note that if $(i, i) \in E$ then there is a **self-loop**, that is, an element is connected to itself via an edge (that ends up looking like a loop). A graph with no loops is called a **multigraph** whereas a **pseudograph** is a graph having at least one loop. The definition of an undirected graph prohibits undirected graphs from having self loops.

In general, $E \subseteq V \times V$, so $|E| \leq |V|^2$.

A sequence of vertices $\langle u_{1}, u_{2}, \ldots, u_{k} \rangle$ in a given graph is a **path** if there is no repetition of vertices in the sequence (that is $u_{i} \neq u_{k}$ $\forall i \neq k$) and for every $1\leq i \leq k-1$, $(u_{i}, u_{i+1}) \in E$. Thus, $\langle u_{1}, u_{2}, \ldots, u_{k} \rangle$ is a path from $u_{1}$ to $u_{k}$.

A sequence of vertices $\langle u_{0}, u_{1}, \ldots, u_{k} \rangle$ in a given graph is a **cycle** if there is no repetition of vertices in the sequence and for every $0\leq i\leq k$, we have $(u_{i \mod k}, u_{(i+1) \mod k}) \in E$. Equivalently, a cycle is sequence of vertices $\langle u_{0}, u_{2}, \ldots, u_{k} \rangle$ such that $u_{0} = u_{k}$ and there is no repetition of vertices in $\langle u_{0}, u_{1}, \ldots, u_{k-1} \rangle$ and $(u_{i}, u_{i+1}) \in E$ $\forall 0\leq i\leq k-1$.

A graph is **connected** if there exists a path connecting any pair of vertices. A graph is **complete** if there exists an edge connecting every pair of vertices in the graph. Clearly, a complete graph is connected but the converse is not true in general (e.g. consider a square with no diagonals).

A **subgraph** of $G = (V, E)$ is a graph $G' = (V', E')$ such that $V' \subseteq V$ and $E' \subseteq E$. By definition, it is also required that $E' \subseteq V' \times V'$. It is obvious that $E' \subseteq V \times V$. A **symmetric digraph** is a directed graph such that for every edge $(v, w)$ there is also the reverse edge $(w, v)$. Every undirected graph has a corresponding symmetric digraph by interpreting each undirected edge as a pair of directed edges in opposite directions.

A **connected component** of an undirected graph G is a *maximal* connected subgraph of G.

**Under Construction**