Complete and bipartite graph

Complete graph Kₙ

A simple graph in which every pair of distinct vertices is joined by exactly one edge.

• n vertices, n(n − 1)/2 edges, each vertex has degree n − 1 (so it is regular).
• χ(Kₙ) = n; K₁, K₂, K₃, K₄ are planar; K₅ and larger are not.

 K3:  a           K4:  a ---- b
     / \               | \  / |
    b---c              |  \/  |
                       |  /\  |
                       d ---- c

(K₄ is drawn with both diagonals.)

Bipartite graph

A graph whose vertices can be divided into two disjoint sets V₁ and V₂ such that every edge joins a vertex in V₁ to one in V₂.

• It is bipartite if and only if it has no odd cycle, or equivalently it is 2-colorable.
• A complete bipartite graph K_{m,n} has all mn edges between V₁ (m vertices) and V₂ (n vertices).

Example K_{2,3}: V₁ = {a, b}, V₂ = {x, y, z}, with edges from each of a and b to each of x, y, z (6 edges). K₃,₃ has 9 edges and is non-planar.