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.

The complete graph K_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}.

The complete bipartite graph K_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.

A graph has a Euler circuit iff it is connected and every vertex has even degree.

Hamiltonian Circuit

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

Every complete graph (n > 2) has a Hamilton circuit.