Complete graph

A simple graph where any one node has a connection to all other nodes. The complete graph with $n$ vertices is sometimes denoted $K_n$.

Properties

• if $n>2$, then it is always cycle (contains a cycle)

Degree of one node

The degree of any one node is equal to the total amount of nodes minus one:

$$Deg(N[k])=|N|-1,k\in \mathbb{N},k\le |N|$$

Number of edges

The number of edges within a complete graph is given by $$ |E|=\frac{|N|(|N|-1)}2

## Cayley's formula (not in study design) Within a complete graph with $V$ vertices, there are exactly $V^{V-2}$ [[Tree|trees]] within the graph. This also counts the number of [[Spanning tree|spanning trees]] (note: not [[Minimum spanning tree|MST]]!) ## Example ![[complete_graph_examples.png|500]]