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