Fully Connected Graphs and Combinatorial Growth

Introduction to Graph Theory

In graph theory, a graph $G$ is a collection of vertices (or nodes) and edges (or links) that connect pairs of vertices. Graphs are fundamental structures in computer science, mathematics, and other fields.

Definition of a Fully Connected Graph

A fully connected graph, also known as a complete graph, is a graph in which every pair of distinct vertices is connected by a unique edge. The complete graph with $n$ vertices is denoted by $K_{n}$ .

Examples of Fully Connected Graphs

$K_{1}$ : A single vertex with no edges.
$K_{2}$ : Two vertices with one edge connecting them.
$K_{3}$ : Three vertices, each connected to the other two, forming a triangle.
$K_{4}$ : Four vertices, each connected to the other three, forming a tetrahedron.

Here are fully connected graphs from $n = 3$ to $n = 10$ :

3 vertices, 3 edges

4 vertices, 6 edges

5 vertices, 10 edges

6 vertices, 15 edges

7 vertices, 21 edges

8 vertices, 28 edges

9 vertices, 36 edges

10 vertices 45 edges

Visualizing Edges

The number of edges in a complete graph $K_{n}$ is given by the combinatorial formula $(2 n)$ , pronounced "n choose 2". This formula represents the number of ways to choose 2 vertices from $n$ vertices, which corresponds to the number of unique edges in the graph. This is "all possible unique pairs for a group." You could think of this as all the possible teams of 2 from the people in a classroom.

Calculation of n choose 2

The formula for $(2 n)$ is:

$(2 n) = \frac{n ( n - 1 )}{2}$

This formula can be derived from the basic principles of combinations, where we choose 2 vertices out of $n$ without regard to the order of selection.

Examples of Edge Calculations

For $K_{3}$ there are 3 edges:

$$ \binom{3}{2} = \frac{3 \cdot 2}{2} = 3 $$
For $K_{4}$ there are 6 edges:

$$ \binom{4}{2} = \frac{4 \cdot 3}{2} = 6 $$

Combinatorial Growth

As the number of vertices $n$ increases, the number of edges in $K_{n}$ grows rapidly. This growth is described as combinatorial or quadratic growth, which can be visualized using the parabolic function $\frac{n ( n - 1 )}{2}$ .

Graph of n choose 2

$f (n) = (2 n)$

The graph of the function $\frac{n ( n - 1 )}{2}$ is a parabola, indicating that the number of edges increases much faster than the number of vertices.

You can use https://www.sagemath.org/ to generate images of fully connected graphs with a lot of vertices.

G = graphs.CubeGraph(33)P = G.plot(vertex_labels=False, vertex_size=0, graph_border=True)P.show()

33 fully connected vertices with 33 choose 2 = 538 edges

Formal Definition and Terminology

The rapid growth in the number of edges in a complete graph is formally known as quadratic growth due to the $n^{2}$ term in the formula for $(2 n)$ . This is distinct from exponential growth, where the growth rate would be proportional to a constant power of $n$ .

Conclusion

Fully connected graphs $K_{n}$ are fundamental in graph theory and combinatorics. Understanding their structure and the combinatorial growth of their edges helps in comprehending more complex graph-theoretic concepts. The visualization of these graphs, especially as $n$ increases, highlights the rapid increase in complexity, reinforcing the importance of combinatorial mathematics in various applications.