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.
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 Km,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}.
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)