📂Graph Theory

Null Graphs and Complete Graphs

Definition ¹

Given a simple graph $G$.

1. If $E(G) = \emptyset$, then $G$ is called a null graph.
2. 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.