A *graph* is an interesting and useful mathematical structure that can describe a network of connections between pairs of nodes. In a graph, we refer to the nodes as *vertices*, and the connections between pairs of vertices we call *edges*.

two drawings of the same graph

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

Graphs have many practical applications -- maps, web content, schedules, social networks, etc.

In some cases, one finds it natural to associate each connection with a direction -- such as a graph that describes traffic flow on a network of one-way roads. Here the edges are the roads themselves, while the vertices are the intersections and/or junctions between these roads. When each connection in a graph has a direction, we call the graph a *digraph*.

In other cases, it is more natural to associate with each connection some numerical "weight". Such graphs are called *edge-weighted graphs*. As an example, when describing a neural network, some neurons are more strongly linked than others. If the vertices of the graph represent the individual neurons, and edges represent connections between pairs of neurons, than the weight of an edge might measure the strength of the connection between two associated neurons.

Still other graphs might require both elements described above. Not surprisingly, such graphs are called *edge-weighted digraphs*. Appealing to economics this time for an example, note that a graph could be used to describe the flow of money between a group of individuals in a given time period. Using vertices to represent the individuals involved, two vertices could be connected if any money flowed from one to the other. The net amount of money that changed hands provides a weight for the edges of such a graph, and the direction of the connection could point towards the vertex that saw a net gain from the associated transactions.

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. As examples, in the graph drawn below, vertices $3$ and $4$ are adjacent, while $1$ and $6$ are not. Edge *d* is incident to vertices $0$ and $6$, but is not incident to any other vertices.

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 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 graphs that are not connected necessarily consist of a set of *connected components*.