Nodes and Connections in a Complete Graph

Definition

A complete graph is a graph in which each vertex is connected to every other vertex by exactly one edge. Throughout this essay, the terms “node” and “vertex”, as well as “connection” and “edge”, are used interchangeably.

\(n\) Nodes: How Many Connections \(k\)?

Figure 1: Visualising network accumulation: 1 + 2 + 3 + 4 = 10 total connections.

For a graph with \(n\) vertices, the number of edges can often be analysed using the degree-edge formula. In the special case of a complete graph, however, the count is especially simple: since every pair of distinct vertices is joined by an edge, the total number of connections is \[\begin{equation*} \binom{n}{2} = \frac{1}{2}n(n-1). \end{equation*}\]

This is also the sum of the first \(n-1\) natural numbers. A simple way to see this is through an accumulation argument.

Suppose we begin with a complete graph on \(r-1\) vertices and then add one new vertex. To preserve completeness, the new vertex must be connected to each of the existing \(r-1\) vertices, so exactly \(r-1\) new edges are added.

Starting from the smallest cases:

• when \(r=1\), there are \(0\) edges;
• when \(r=2\), \(1\) new edge is added;
• when \(r=3\), a further \(2\) edges are added, giving \(3\) in total.

Continuing in this way, and formalising the pattern by induction if desired, we obtain the number of edges in a complete graph with \(n \in \mathbb{N}\) vertices: \[\begin{equation*} k = \sum_{r=1}^{n}(r-1) = 1+2+\cdots+(n-1) = \frac{1}{2}n(n-1). \end{equation*}\]

To illustrate this visually, we look at the case of 5 nodes in Figure 1:

• Start with node \(v_1\). When adding \(v_2\), 1 connection is established between them (red).
• Add \(v_3\), creating an additional 2 connections from \(v_1\) and \(v_2\) to \(v_3\) (orange).
• Add \(v_4\), establishing a further 3 connections from \(v_1\), \(v_2\), and \(v_3\) to \(v_4\) (teal).
• Finally, add \(v_5\) for the final 4 connections from \(v_1\), \(v_2\), \(v_3\), and \(v_4\) to \(v_5\) (cyan).

\(k\) Connections: How Many Nodes \(n\)?

If the number of connections \(k\) is known, we must solve the formula derived above for \(n\):

\[ \frac{1}{2}n(n-1) = k \]

Using the quadratic formula, the solution for the number of nodes with \(k\) connections in a complete graph is:

\[ n = \frac{1+\sqrt{1+8k}}{2} \]

As a graph cannot contain a fractional number of nodes, to guarantee at least \(k\) connections we use the ceiling function \(\lceil \cdot \rceil\) to round up to the nearest integer:

\[ n = \left\lceil \frac{1+\sqrt{1+8k}}{2}\right\rceil \]

For example, if we require at least one hundred connections (\(k=100\)), then

\[ n = \left\lceil \frac{1+\sqrt{1+800}}{2}\right\rceil = 15 \]

In fact, \(n=15\) corresponds exactly to:

\[ k = \frac{1}{2}\cdot 15\cdot14 = 105 \]

connections.

Asymptotics and Geometry of Connections

The number of connections \(k\) in a complete graph grows asymptotically as \[\begin{equation*} k = \frac{1}{2}n(n-1) \sim \frac{1}{2}n^2. \end{equation*}\]

Thus, the number of edges increases quadratically with the number of vertices, so \(k = \mathcal{O}(n^2)\). The leading term \(\frac{1}{2}n^2\) captures the dominant growth, although the absolute error remains linear in \(n\): \[\begin{equation*} \left| \frac{1}{2}n(n-1) - \frac{1}{2}n^2 \right| = \frac{1}{2}n. \end{equation*}\]

Accordingly, the absolute error diverges as \(n \to \infty\), but the relative error tends to zero. In this asymptotic sense, \(\frac{1}{2}n^2\) becomes an increasingly accurate approximation.

Let \(K_n\) denote the complete graph on \(n\) vertices. When the vertices of \(K_n\) are arranged symmetrically on a circle and all edges are drawn as straight chords, an interesting geometric distinction emerges between the cases where \(n\) is even and where \(n\) is odd:

• For even \(n\): some edges are true diameters of the circle, and these intersect at the exact centre. This produces a sharp central intersection point, with additional layers of overlapping chords arranged around it.

• For odd \(n\): no pair of vertices is diametrically opposite, so no edge passes exactly through the centre. As a result, a small circular void remains at the centre. Although this empty region decreases in size as \(n\) increases, it remains visually distinct from the even case.

• As \(n \to \infty\): the vertices become dense on the circle, and the increasing number of chords produces an ever finer mesh.

Figure 2: Close-up view of large complete graphs \(K_{10}\) through \(K_{15}\). Notice the visual contrast at the absolute center between the even graphs \(K_{10}, K_{12}, K_{14}\), which possess a sharp central intersection point, and the odd graphs \(K_{11}, K_{13}, K_{15}\), which maintain a completely clear, circular void in the middle.

At a sufficiently abstract level, one may view the universe through the lens of a complete graph. If vertices represent atoms or particles, and an edge is interpreted broadly as some form of physical relation between two entities, then every pair may be regarded as connected.