An interactive introduction to aspects of graph theory using the Cytoscape.js library.

Given a graph
\(G=(V,E)\) comprising a set of vertices \(V\) and edges \(E\), the **degree** \(d(v)\) of a vertex
\(v\in V\) is the number of edges incident to \(v\); that is, the number of neighbours of \(v\).
The **degree sequence** of \(G\) is then the sequence
\[\left(d(v_1),d(v_2),\ldots,d(v_n)\right) \qquad d(v_1)\geq d(v_2) \geq\ldots \geq d(v_n)\]

*Try it yourself.*
Use the below widget to create a graph
and check you agree with the degree sequence shown.

Click anywhere to add a vertex and click successive vertices to create an edge.

On the other hand, one may ask whether, for a finite sequence of non-negative integers
\(\left(d_1,d_2,\ldots,d_n\right)\), there exists a graph with degree sequence \(\left(d_1,d_2,\ldots,d_n\right)\).
This is the **graph realisation problem.**

It should be apparent that existence is not guaranteed.
For example, \(\left(0,1\right)\) clearly cannot be the degree sequence of any (simple) graph.
We say that \(\left(0,1\right)\) is **non-graphic.**

Beyond consisting of non-negative integers only,
a most basic *necessary* condition for a degree sequence to be graphic
comes from the **handshaking lemma,** which states that the sum of all degrees
equals twice the number of edges:
\[\sum_{v\in V}d(v) = 2 \lvert E \rvert\]
Consequently, \(\sum_{v\in V}d(v)\) must be *even.*
This allows us to immediately discount the sequence \(\left(3,2,1,1\right)\), for example,
but not \(\left(3,1,1,1\right)\).
In fact, the latter *is* graphic:

How might we verify this without actually constructing the graph?

The **Erdős-Gallai theorem** provides a solution to the graph realisation problem.
It may be stated as follows:

A non-increasing sequence of non-negative integers \(\left(d_1,d_2,\ldots,d_n\right)\) is the representation of a graph on \(n\) verticesif and only if\(\sum_{i=1}^n d_i\) is even and \[\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min\left\{d_i,k\right\}\] for each \(k \in \{1,\ldots,n\}\).

Take the sequence \((3,1,1,1)\). As \(d_1=3\) and \(d_2=d_3=d_4=1\), at each \(k \in\{1,2,3,4\}\) we have \(\min\left\{d_i,k\right\} = 1\) whilst \[ \sum_{i=1}^4d_i = 6 \] is even. Then \[ \begin{align} k=1:\qquad& d_1=3\leq 1(0) + \sum_{i=2}^41 = 3 \\ k=2:\qquad& d_1+d_2=4\leq 2(1) + \sum_{i=3}^41 = 4 \\ k=3:\qquad& d_1+d_2+d_3=5\leq 3(2) + \sum_{i=4}^4 1 = 7\\[8pt] k=4:\qquad& d_1+d_2+d_3+d_4=6\leq 4(3) = 12, \end{align} \] confirming that this sequence is graphic.

*Try it yourself.*
Come up with several sequences and determine whether they are graphic using the Erdős-Gallai theorem.
Use the below tool to check your answers.

While the Erdős-Gallai theorem provides an efficient test as to whether a sequence is graphic,
it does not provide a means of constructing a graph with that degree sequence in the case of a positive result.
In contrast,
the **Havel-Hakimi algorithm** provides a *constructive* solution to the graph realisation problem.
It is a recursive algorithm based on the following theorem:

A non-increasing sequence \(S=\left(d_1,d_2,\ldots,d_n\right)\) of non-negative integers is graphicif and only ifthe sequence \[S'=\bigl(\underbrace{d_2-1,d_3-1,\ldots,d_{d_1+1}-1}_{d_1 \ \text{terms}},d_{d_1+2},\ldots,d_n\bigr)\] comprises non-negative integers and (when sorted) is graphic.

Equipped with this theorem, the procedure to check whether a given sequence \(S_0=\left(d_1,d_2,\ldots,d_n\right)\) is graphic is straightforward:

- Remove the first element \(d_1\) of \(S_0\) and subtract 1 from the next \(d_1\) elements, sorting the remaining elements to form a non-increasing sequence \(S_1\). If this is not possible (there are fewer than \(d_1\) terms in the truncated sequence) or \(S_1\) contains a negative integer, \(S_1\), and therefore \(S_0\), is non-graphic.
- Repeat to generate \(S_2,S_3,\ldots\). If at any stage there are too few terms to subtract 1 from, or a non-negative integer is encountered, the original sequence is non-graphic. Otherwise, after at most \(n-1\) steps, a sequence \(S_F\) of zeros will result. As \(S_F\) clearly has a graphical representation (a collection of 1 or more unconnected vertices), so does \(S_0\).

Graphically, in the \(i^{\text{th}}\) iteration we attach the vertex with the greatest degree \(d(v_{\text{max}})\) to the \(d(v_{\text{max}})\) vertices of next greatest degree, repeating until we either cannot 'exhaust' a particular vertex (i.e. it has a degree larger than the sum of degrees of the remaining vertices) and the algorithm fails to produce a graph, or we reach a situation where none of remaining vertices require further neighbours (\(S_F=(0,\ldots,0)\)), and a graph has been completed.

In fact, in each iteration one is free to chose *any* one of the \(d_i\) to be removed, provided it is
still the *greatest* \(d_i\) terms that are decremented,
with different choices at each step producing a variety of graphical representations.

As a demonstration, consider the sequence \(S_0=\left(3,2,2,1,1,1\right)\). The labels \(v_0,\ldots,v_5\) will be used to keep track of the vertices as in \[S_0 =(\overset{v_0}{3},\overset{v_1}{2},\overset{v_2}{2},\overset{v_3}{1},\overset{v_4}{1},\overset{v_5}{1})\]

- Attach \(v_0\) to \(v_1\), \(v_2\) and \(v_3\). Remember to sort the truncated sequence: \[S_1=(\overset{v_1}{1},\overset{v_2}{1},\overset{v_3}{0},\overset{v_4}{1},\overset{v_5}{1} )\to (\overset{v_1}{1},\overset{v_2}{1},\overset{v_4}{1},\overset{v_5}{1},\overset{v_3}{0})\]
- Attach \(v_1\) to \(v_2\): \[S_2=(\overset{v_2}{0},\overset{v_4}{1},\overset{v_5}{1},\overset{v_3}{0}) \to(\overset{v_4}{1},\overset{v_5}{1},\overset{v_2}{0}, \overset{v_3}{0})\]
- Finally, join \(v_4\) and \(v_5\): \[S_3=(\overset{v_5}{0},\overset{v_2}{0},\overset{v_3}{0})=S_F\]

\(S_0 =(\overset{v_0}{3},\overset{v_1}{2},\overset{v_2}{2},\overset{v_3}{1},\overset{v_4}{1},\overset{v_5}{1})\)

\(S_1 = (\overset{v_1}{1},\overset{v_2}{1},\overset{v_4}{1},\overset{v_5}{1},\overset{v_3}{0})\)

\(S_2 = (\overset{v_4}{1},\overset{v_5}{1},\overset{v_2}{0}, \overset{v_3}{0})\)

\(S_3=(\overset{v_5}{0},\overset{v_2}{0},\overset{v_3}{0})\)

Observe that the graph produced is not *connected* (no path exists between \(v_4\) and \(v_0\), for example).
As mentioned above, it is not necessary to select the greatest term for removal with each iteration.
It turns out that if instead the *least* term is chosen each time, the resulting
graph will always be connected *if* a connected realisation exists.

*Try if for yourself.*
The below widget performs the Havel-Hakimi algorithm to produce a connected graph from any degree sequence.
Come up with a valid degree sequence and see if you can
match its output.