Tags: #definition

complete graph

The complete graph on $n$ vertices is a graph $G=(V,E)$ where $|V|=n$ and there is an edge between every pair of vertices in the graph.

Properties

• The number of spanning trees on $K_n$ is $\frac{1}{n}{n}^{n-1}=n^{n-2}$
  • This is equivalent to Cayley's formula
• $f_{K_n}(x)=(x+n{)}^{n-1}$
  • This follows from noting that $K^n$ is the complement of the graph with $n$ vertices and no edges, which has f_G $x^{n-1}$