Bringing graphs to the digital age

Would you like to know more?

We can represent relationships among elements using graphs, e.g., traveling routes among cities, chemical bonds between atoms, links between websites, relationships among friends and family, etc. So far we have seen the analog graphical representations of graphs, i.e., drawings of dots, which represent elements, connected by arrows or edges, which represent one- or two-way relationships. We need to represent these elements and relationships digitally, as numbers, to study graphs using a computer.

The graphs that we have seen so far do not have labeled vertices or edges, i.e., they are unlabeled graphs. To study and storage graphs we can label their vertices, thus obtaining a labeled graph. The order \(n\) of a graph is the number of vertices that it has; we will label these \(n\) vertices as \({0, 1, …, n-1}\), and refer to them as \(v_0\), \(v_1\), …, \(v_{n-1}\). Another possibility is to label the edges, but such representation is less common than labeling the vertices.

Once we have labeled the vertices of a graph, we can represent it using an adjacency vertex list, or AVL. We say that a vertex \(v_i\) is adjacent to a vertex \(v_j\) if there is an arc from \(v_i\) to \(v_j\); the fact that \(v_i\) is adjacent to \(v_j\) doesn’t mean that \(v_j\) is adjacent to \(v_i\). If \(v_i\) and \(v_j\) are connected by an edge, then the connection is symmetric because an edge is simply two arcs traveling in opposite directions between those two vertices, i.e., there is an arc from \(v_i\) to \(v_j\) and another from \(v_j\) to \(v_i\); we count separately each arc between any two vertices.

The adjacency vertex list (AVL) is usually simply called the adjacency list, but we specify it here because there is also an adjacency edge list, which is used much less often, as we usually label the vertices of the graphs instead of their edges.

Let’s represent an unlabeled simple undirected graph with an AVL. First we label the vertices in an arbitrary way, e.g., we’ll label them counterclockwise starting from the top. Then we think of the edges as arcs so we can tell the adjacency between vertices.

Let’s call the graph above \(G\), our default name for a graph; it’s AVL is

$$
\begin{array}{ll}
0:&1,4\\
1:&0,2,4\\
2:&1,3\\
3:&2,4\\
4:&0,1,3\\
\end{array}
$$

or, as a one-liner represented with a Python hash table:

{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # G

We could have represented the AVL using a list, but the hash table representation lets us see at a glance the adjacent vertices of a particular vertex, e.g., there is an arc from \(v_2\) to each of \(v_1\) and \(v_3\). The # character at the end of the one-liner AVL and the text that follows it are a Python comment; we can ignore it or omit it.

Now that we can identify individual vertices, we can characterize them. The most basic feature of a vertex is its degree, a.k.a. its valency. If we are dealing with a digraph, the out-degree is the number of arcs that leave the vertex, while the in-degree is the number of arcs that arrive to it; if we are dealing with an undirected graph, the out-degree is the same as the in-degree, so we just call it the degree of the vertex, and we can define it simply as the number of edges connected to the vertex. For example, for our graph \(G\), the degree of \(v_0\) is 2, while the degree of \(v_1\) is 3.

A more general example is that of an unlabeled disconnected pseudo digraph with multiple loops, edges and isolated vertices. Again, we label the vertices in an arbitrary fashion, and then we recast the edges as arcs to find the vertex adjacency and arc multiplicity. For visualization purposes, we have colored the multiplicity tick marks in red. Again, let’s call it graph \(G\).

The AVL of the pseudograph \(G\) above is

{0:[], 1:[4], 2:[1,1,2,2,2,2,2,2,3], 3:[2,4,4], 4:[1,3,3,4]} # G

Vertex 0 has no adjacent vertices so its list is empty. For \(v_1\), there is one arc to \(v_4\). For \(v_2\), there are two arcs to \(v_1\), six arc loops from the three edge loops, and an arc to \(v_3\). For \(v_3\), there is an arc to \(v_2\) and two arcs to \(v_4\). And, finally, for \(v_4\) there is an arc to \(v_1\), two arcs to \(v_3\), and an arc loop.

Even though the subjects of graph theory are the abstract mathematical unlabeled graphs composed of a set of vertices and a set of connections between those vertices, we label them to study them. From here on, unless we specify otherwise, we will use the word “graph” to refer to graphs with labeled vertices, i.e., to labeled graphs.

Examples

The following are the AVLs of the graphs we saw in the definition page. We label the vertices counterclockwise, starting from the top, but this is arbitrary; all labelings are equivalent and represent the unlabeled graph equally well.

Simple connected graphs

{0:[1,4], 1:[0,2,4], 2:[1,3], 3:[2,4], 4:[0,1,3]} # a
{0:[1,4], 1:[], 2:[1,3], 3:[], 4:[1,3]}           # b
{0:[1,4], 1:[2,4], 2:[1,3], 3:[4], 4:[1,3]}       # c

{0:[1], 1:[0]} # a
{0:[1], 1:[0]} # b

As expected, these two AVLs are identical since they are simply two different graphical representations of the same graph.

Simple disconnected graphs

{0:[1], 1:[2], 2:[], 3:[], 4:[3]}      # a
{0:[], 1:[], 2:[1,3], 3:[], 4:[1,3]}   # b
{0:[], 1:[2], 2:[], 3:[4], 4:[]}       # c

Multigraphs and multidigraphs

{0:[1], 1:[0,2,2], 2:[1,1]} # a
{0:[1], 1:[0,2,2], 2:[1,1]} # b

{0:[], 1:[0,0,0]} # a
{0:[], 1:[0,0,0]} # b

Loops

This is the simplest graph with a loop:

{0:[0]}

Pseudographs

{0:[], 1:[4], 2:[1,3], 3:[2,4], 4:[1,3,4]}                  # a
{0:[], 1:[4], 2:[1,1,3], 3:[4], 4:[1,3]}                    # b
{0:[], 1:[4], 2:[1,1,2,2,2,2,2,2,3], 3:[2,4,4], 4:[1,3,4]}  # c

First published on Dec. 19/2025