Simple Graph of Maximum Size is Complete Graph/Examples

Examples of Use of Simple Graph of Maximum Size is Complete Graph

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