# Degree

## Definitions

### Regular Graph

If a graph in which every vertex has degree k, for some fixed k, is called a k-regular graph (or a regular graph)

## Theorems

### Handshaking Lemma (Degree-Sum Formula)

$$
\underset{v \in V(G)}{\Sigma} deg(v) = 2|E(G)|
$$

### The average degree of a vertex in the graph G

$$
\frac{2|E(G)|}{|V(G)|}
$$

### Corollary

The number of vertices of odd degree in a graph is even.

# Bipartite Graphs

## Definitions

### Bipartite

A graph in which the vertices can be partitioned into two sets A and B, so that all edges join a vertex in A to a vertex in B, is called a bipartite graph, with bipartition (A, B).

## Lemma

- An odd cycle is not bipartite