### Formula Review

### 12.2 Graph Structures

For the Sum of Degrees Theorem, $\mathrm{sum\; of\; the\; degrees}=2\times \mathrm{number\; of\; edges}$ or $\mathrm{number\; of\; edges}=\frac{\mathrm{sum\; of\; degrees}}{2}$

The number of edges in a complete graph with $n$ vertices is the sum of the whole numbers from 1 to $n-1$, $1+2+3+\cdots +(n-1)$.

The number of edges in a complete graph with $n$ vertices is $1+2+3+\cdots +(n-1)=\frac{n(n-1)}{2}$.

### 12.7 Hamilton Cycles

The number of ways to arrange $n$ distinct objects is $n!$.

The number of distinct Hamilton cycles in a complete graph with $n$ vertices is $\left(n-1\right)!$.

### 12.9 Traveling Salesperson Problem

- In a complete graph with $n$ vertices, the number of distinct Hamilton cycles is $\left(n-1\right)!$.
- In a complete graph with $n$ vertices, there are at most $\frac{(n-1)!}{2}$ different weights of Hamilton cycles.

### 12.10 Trees

- The number of edges in a tree graph with $n$ vertices is $n-1$. A connected graph with n vertices and $n-1$ edges is a tree graph.