A **graph** is an interesting and useful mathematical structure that can describe a network of connections between pairs of nodes. They provide an extremely useful abstraction for representing data in a variety of contexts and practical applications.

In a graph, we refer to the nodes as **vertices**, and the connections between pairs of vertices we call **edges**.

We can gain some intuition about the structure of a graph by drawing it as a collection of labeled dots (vertices) and connecting lines (edges). However, one should be aware that any given graph can be drawn in many different ways, as the graphic below demonstrates. The specific positions of the nodes is generally not relevant. We instead focus solely on the connections between the nodes present. As can be seen below, these are preserved despite the nodes being drawn in different places.

*Two drawings of the same graph*

The following notes some specific contexts in which the use of graphs can be helpful, noting specifically what plays the role of a vertex and what plays the role of an edge in each:

Context | Vertex | Edge |
---|---|---|

communication | telephone, computer | fiber optic cable |

electric circuits | gate, register, processor | wire |

transportation | intersection | road |

board game | game piece position | legal move |

social network | person | friendship |

neural network | neuron | synapse |

map | state, country | shared border |

molecule | atom | bond |

protein network | protein | protein-protein interaction |

In a graph, when there is an edge connecting two vertices, the vertices are said to be **adjacent** to one another and the edge is **incident** to both vertices. Similarly, **adjacent edges** are edges that share a common vertex. As some examples seen in the graph below, vertices $3$ and $4$ are adjacent, while $1$ and $6$ are not. Further, edge *d* is incident to vertices $0$ and $6$, but is not incident to any other vertices, although it is adjacent to edges $a$, $e$, $f$, and $c$.

Two edges that connect the same pair of vertices are called **parallel**, while an edge that connects a vertex to itself is called a **loop**. The **degree** of a vertex is the number of edges incident to that vertex, with loops counted twice. So, the degree of vertex $0$ in the graph below is $5$, while the degree of vertex $1$ in the same graph is $3$.

A **subgraph** is a subset of a graph's edges (and associated vertices) that constitutes a graph.

A *path* in a graph is a sequence of vertices connected by edges. A **simple path** is one with no repeated vertices. When the first and last vertices of a path (of at least one edge) are the same, we call the path a **cycle**. A **simple cycle** is a cycle with no repeated vertices or edges (except the first and last vertices). An graph is said to be **acyclic** if it contains no cycles. The **length** of a path or cycle is its number of edges.

One vertex is said to be **connected to** another if there exists a path that contains them both. More generally, we say a graph is **connected** if there is a path from every vertex in the graph to every other vertex in the graph. Note, that a graph that is not connected necessarily consists of a set of **connected components**. As an example, note how the graph on $29$ vertices below is a set of three connected components (of $4$, $16$, and $9$ vertices).