Counting All Subgraphs in a Complete Graph with Adjacency Matrices

Complete graph \(k_6\)

A complete graph \(k_n\) can be represented by a \(n \times n\) symmetric adjaceny matrix.

\begin{equation*} k_n = \begin{pmatrix} 0 & e_1 & e_2 & … & e_n \\
e_1 & 0 & & & \\
e_2 & & 0 & & \\
\vdots & & & \ddots & \\
e_n & & & & 0 \end{pmatrix} \end{equation*}

The upper (or lower) triangle will have \(\frac{{n(n-1)}}{2}\) components. Flatten this triangle into a bit string, and then there are \(2^{ \frac{{n(n-1)}}{2} }\) spanning subgraphs. (\(n\) 0’s to \(n\) 1’s, which represent a triangle of all 0’s to a triangle of all 1’s.)

Then, apply this to all \(k_n\) from \(n\) down to 1.

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

This sum represents the number of subgraphs in \(k_n\).


An example with \(k_4\):

\begin{equation*} k_4 = \begin{pmatrix} 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \end{pmatrix} \end{equation*}

Because the matrix is symmetrical, we only need to consider the upper triangular matrix \(U_4\).

\begin{equation*} U_4 = \begin{pmatrix} 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \end{pmatrix} \end{equation*}

Flatten this into a bit string of 6 bits:

$$ b(U_4) = 111111 $$

Where \(| b(U_4) | = \frac{{n(n-1)}}{2} = \frac{{4(3)}}{2} = 6\).

Then you can represent all spanning subgraphs as 000000, 000001, 000010, … 111111.

6 bits can represent \(2^{| b(U_4) |} = 2^{6}\) graphs this way.

Then repeat these steps for \(k_3, k_2, k_1\). Then sum the following:

$$ \sum_{k=1}^{4} 2^{ | b(U_k) | } = \sum_{k=1}^{4} 2^{ \frac{{k(k-1)}}{2} } = 2^0 + 2^1 + 2^3 + 2^6 = 75 $$

There are 75 subgraphs in \(k_4\).