Problem
COM-B1-M09-P011 Too Many Edges
#11
★★☆☆☆ Level 2 of 5
Can a simple graph on \(8\) vertices have \(29\) edges?
The maximum is achieved by the complete graph.
In a simple graph, there is at most one edge between two vertices. The maximum number of edges is in the complete graph \(K_8\), which has \(\binom{8}{2}=28\) edges. Therefore \(29\) edges are impossible.
Clarifies the phrase “simple graph”.