Contemporary Mathematics

# Formula Review

### 12.2Graph Structures

For the Sum of Degrees Theorem, $sum of the degrees=2×number of edgessum of the degrees=2×number of edges$ or $number of edges=sum of degrees2number of edges=sum of degrees2$

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

The number of edges in a complete graph with $nn$ vertices is $1+2+3+⋯+(n−1)=n(n−1)21+2+3+⋯+(n−1)=n(n−1)2$.

### 12.7Hamilton Cycles

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

The number of distinct Hamilton cycles in a complete graph with $nn$ vertices is $(n−1)!(n−1)!$.

### 12.9Traveling Salesperson Problem

• In a complete graph with $nn$ vertices, the number of distinct Hamilton cycles is $(n−1)!(n−1)!$.
• In a complete graph with $nn$ vertices, there are at most $(n−1)!2(n−1)!2$ different weights of Hamilton cycles.

### 12.10Trees

• The number of edges in a tree graph with $nn$ vertices is $n−1n−1$. A connected graph with n vertices and $n−1n−1$ edges is a tree graph.
Order a print copy

As an Amazon Associate we earn from qualifying purchases.