Graph Counting

Graph counting, a cornerstone of graph theory and combinatorics, enumerates graphs based on vertices, edges, and properties like connectivity or labeling. Graphs model networks, molecules, and social systems, and counting them answers questions like "How many distinct trees exist with \( n \) vertices?" This MathMultiverse guide explores complete graphs, bipartite graphs, trees, labeled and unlabeled graphs, with formulas, examples, and applications in network design and chemistry, enhanced with interactive visualizations.

Graph Basics and Counting

Complete Graphs

Edges in \( K_n \):

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

For \( n = 5 \):

\[ E = 10 \]

Labeled Graphs

Simple graphs with \( n \) vertices, \( m \) edges:

\[ \binom{\binom{n}{2}}{m} \]

Total labeled graphs:

\[ 2^{\binom{n}{2}} \]

Trees

Cayley’s formula for labeled trees:

\[ n^{n-2} \]

Bipartite Graphs

Edges in \( K_{m,n} \):

\[ E = m \cdot n \]

Unlabeled Graphs

Burnside’s lemma:

\[ \frac{1}{|G|} \sum_{g \in G} \text{fix}(g) \]

Labeled Trees Growth

Number of labeled trees by vertices.

Examples

Complete Graph

Edges in \( K_6 \):

\[ E = \frac{6 \cdot 5}{2} = 15 \]

Labeled Graphs

Graphs with 4 vertices, 3 edges:

\[ \binom{6}{3} = 20 \]

Trees

Labeled trees with 5 vertices:

\[ 5^3 = 125 \]

Bipartite Graph

Edges in \( K_{2,3} \):

\[ 2 \cdot 3 = 6 \]

Applications

Network Design

Topologies for 5 nodes:

\[ 2^{10} = 1024 \]

Chemistry

Isomers of pentane: 3 unlabeled trees.

Social Networks

Triads in 3 nodes:

\[ \binom{3}{2} = 3 \]