Null Graphs and Complete Graphs
Definition 1
Given a simple graph $G$.
- If $E(G) = \emptyset$, then $G$ is called a null graph.
- If $E \left( \overline{G} \right) = \emptyset$, then $G$ is called a complete graph.
Description
A null graph is literally an empty graph. The reason why we use the term Null instead of Empty is that even if $G \ne \emptyset$, it has no meaning as a graph. For example, if there are only vertices like the following picture, there is hardly a reason to call it a graph. However, similar to how the number $0$ is incredibly important in mathematics, null graphs are very frequently mentioned throughout graph theory.
A complete graph is originally defined as the complement $\overline{G} $ of the original graph $G$. That $\overline{G}$ is a null graph means all vertices of the original graph $G$ are connected without exception. For instance, the following is the complement of the graph above.
Subsequent Definitions
In particular, a complete graph with the number of vertices $n$ is denoted as $K_{n}$.
- If a complete graph is a subgraph of some graph, it is called a clique.
- The largest $n$ of the clique $K_{n}$ in graph $G$ is called the clique number $\omega (G)$ of $G$, and
- The clique number of the complement $\overline{G}$ of $G$ is called the independence number $\beta (G) := \omega \left( \overline{G} \right)$ of $G$.
- Meanwhile, a directed complete graph is called a tournament.
Wilson. (1970). Introduction to Graph Theory: p17. ↩︎