Simple Graph of Maximum Size is Complete Graph/Examples/Order 5
Jump to navigation
Jump to search
Examples of Use of Simple Graph of Maximum Size is Complete Graph
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$.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $18 \ \text {(c)}$