Consider a graph G of 8 vertices containing no self loop. If there is no more than one edge between any pair of vertices, maximum possible number of edges in G are :

Question

Accepted Answer

The correct option is (3):
The question describes a *simple, undirected graph* of 8 vertices. The properties "no self loop" and "no more than one edge between any pair of vertices" are the defining characteristics of a simple graph. To find the *maximum* possible number of edges in such a graph, we must assume it is a *complete graph* ($K\_n$), where every distinct pair of vertices is connected by exactly one edge. The formula to calculate the number of edges ($e$) in a complete graph with $n$ vertices is given by the combination formula, which is the number of ways to choose 2 vertices from $n$: $e = \binom{n}{2} = \frac{n(n-1)}{2}$. Substituting the given number of vertices, $n=8$, we perform the calculation: $e = \frac{8(8-1)}{2} = \frac{8 \times 7}{2} = \frac{56}{2} = 28$. Thus, the maximum possible number of edges is 28.

The incorrect option is (1):
Option 1, 8, is incorrect because it is only the number of vertices, $n$, in the graph. While it is possible to construct a graph with 8 vertices and 8 edges (for example, a path or a cycle graph), this number is clearly not the maximum possible. The question explicitly asks for the *maximum*, and since $28 \> 8$, this option represents a sparse graph, not the most connected one.

The incorrect option is (2):
The value 16 is less than the actual maximum of 28, making it an incorrect answer for the maximum possible edges. It may be a result of confusing the simple graph formula with an incorrect calculation, such as $2n$ or $n \times 2$, which does not apply to this problem. A graph with 16 edges on 8 vertices is possible, but it means that not all pairs of vertices are connected, thus it is not the maximum.

The incorrect option is (4):
Option 4, 64, is derived from the calculation $n^2 = 8^2 = 64$. This is the theoretical maximum number of edges in a graph if it were a *directed graph* that allowed *both* self-loops and multiple directed edges. Since the question specifies an undirected graph with no self-loops and no multiple edges (a simple graph), the maximum number of connections must be $n(n-1)/2$. The value 64 is a gross overestimation that applies to a different, less restricted type of graph model.