## Simple Graph

Aa simple graph is an undirected graph that has no loops and no more than one edge between any two different vertices.

In a simple graph with n vertices, every vertex has a degree that is less than n.

Simple graph must have two vertices of the same degree.

## Complete Graph

A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge.

_{n}on n vertices has n * (n-1)/2 edges.

## Bipartite graph (bigraph)

A bigraph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets. Equivalently, a bigraph is a graph that does not contain any odd-length cycles.

## Complete Bipartite Graph (biclique)

A complete bipartite graph K_{m,n} has a vertex covering number of min{m,n}
and an edge covering number of max{m,n}.

_{m,n}has (m + n) vertices and m * n edges.

Each vertex in m-set has n degree. Each vertex in n-set has m degree.

If m = n, then it has a Hamiltonian Circuit.

If both m and n are even, then it has a Euler Circuit.

## Euler Circuit

In graph theory, an Euler trail is a trail in a graph which visits every edge exactly once. Similarly, an Euler circuit is an Eulerian trail which starts and ends on the same vertex.

## Hamiltonian Circuit

Hamiltonian Circuit is a circuit that visits each vertex once without touching any vertex more than once. (Postman problem)