2.1.5. Special graphs with special notations

A graph G is regular of degree r if for each vertex v of G. Such graphs are called r-regular.

 

A graph is complete if every two of its vertices are adjacent.

Statement 2.4. A complete graph of order n and size m is a regular graph of degree having  edges. We denote this graph by Kn.

A complement of a graph G is that graph  such that , and for any  iff .

Statement 2.5. If G is a graph of order n and size m, then  is a graph of order n and size

Statement 2.6. The complement of the complete graph Kn is the empty graph of order n.

A graph is self-complement if .

Theorem 2.7.  If G is self-complement, then either or .

Proof. If G is a self-complementary graph of order n, then its size is . Since only one of n and n - 1 is even, either or . Therefore, or .

A graph G is k-partite, k1, if it is possible to partition  into k subsets (called partite sets) such that every element of joins a vertex of to a vertex of , .  For k = 2, the graph is called as bipartite graph.

A complete k-partite graph with partite sets and  is k-partite graph having the added property that if and  then . It is denoted by . The complete bipartite graph with  and  is denoted by  or ( is a star).