A Special Complete Bipartite Graph

In December of 2024, I made a post titled Welcoming In 2025 in which I looked at some of the more interesting properties of the number 2025. Recently, in this YouTube video, I came across another interesting property of the number in connection to complete bipartite graphs and spanning trees.

The definition of a complete bipartite graph is a graph where all possible edges connect vertices in two disjoint sets, but no edge connects vertices in the same set. An example is \(K_{3,5} \) shown in Figure 1. The two disjoint sets have 3 and 5 vertices, hence the nomenclature.

A spanning tree is defined as a graph that connects all of a graph's vertices without creating any loops or cycles. It's a subgraph of the original graph, meaning it uses all of the vertices but only some of the edges.

An example of a spanning tree for \(K_{3,5}\) is shown in Figure 2 where the red edges represent the spanning tree.

There is a general formula for calculating the number of spanning trees for a \(K_{m.n} \) bipartite graph and it is:$$s(K_{3,5})=m^{n-1} n^{m-1}$$So in the case of \( K_{3,5} \) we have:$$s(K_{3,5})=3^4 5^2 = 2025$$Thus there are 2025 spanning trees for a complete \(K_{3,5}\) bipartite graph and thus we have another interesting property of this year's number.