2.1.5. Special graphs with special notations

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).