Simple Graph of Maximum Size is Complete Graph
Theorem
Let $G$ be a simple graph of order $n$ such that $n \ge 1$.
Let $G$ have the largest size of all simple graphs of order $n$.
Then:
- $G$ is the complete graph $K_n$
- its size is $\dfrac {n \paren {n - 1} } 2$.
Proof
By definition, $K_n$ is the simple graph of order $n$ such that every vertex of $K_n$ is adjacent to all other vertices.
So, let $G$ have the largest size of all simple graphs of order $n$.
Then by definition of largest size, it is not possible for another edge to be added to $G$.
The only way that could be is if all the vertices of $G$ are already adjacent to all other vertices.
Hence $G = K_n$ by definition.
The size of $G$ then follows from Size of Complete Graph.
$\blacksquare$
Examples
Maximum Size Simple Graph of Order 3
Let $G$ be the simple graph of order $3$ whose edge set $E$ is as large as possible.
Then the size of $G$ is given by:
- $\size E = 3$
Maximum Size Simple Graph of Order 4
Let $G$ be the simple graph of order $4$ whose edge set $E$ is as large as possible.
Then the size of $G$ is given by:
- $\size E = 6$
Maximum Size Simple Graph of Order 5
Let $G$ be the simple graph of maximum size whose vertex set is:
- $V = \set {v_1, v_2, v_3, v_4, v_5}$
Then the edge set $E$ such that $\size E$ is as large as possible is:
- $E = \set {v_1 v_2, v_1 v_3, v_1 v_4, v_1 v_5, v_2 v_3, v_2 v_4, v_2 v_5, v_3 v_4, v_3 v_5, v_4 v_5}$
Thus:
- $\size E = 10$
and it is seen by inspection that $G = K_5$, that is, the complete graph of order $5$.
Also see
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $18 \ \text {(d)}$