Question

How many edges are there in a complete graph with \(n\) vertices?

• A. \(n(n-1)\)
• B. \( \frac{n(n-1)}{2} \)
• C. \(n^2\)
• D. \( \frac{n(n+1)}{2} \)

Hint:

In a complete graph \(K_n\), every vertex connects to all other vertices. Hence, the total number of edges is always \( \frac{n(n-1)}{2} \).

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks for the formula to calculate the number of edges in a complete graph, denoted \(K_n\), which has \(n\) vertices. A complete graph is one where every vertex is connected to every other vertex by a unique edge.
Step 2: Key Formula or Approach:
We can solve this from two perspectives: using combinations or using the handshaking lemma.
Approach 1 (Combinations):
An edge is formed by connecting a pair of vertices. The problem is equivalent to finding how many unique pairs of vertices we can choose from a set of \(n\) vertices. This is a combination problem.
The number of ways to choose 2 vertices from \(n\) is given by "n choose 2":
\[ \binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} \] Step 3: Detailed Explanation:
Approach 2 (Handshaking Lemma):
1. In a complete graph with \(n\) vertices, each vertex is connected to all other \(n-1\) vertices. Therefore, the degree of each vertex is \(n-1\).
2. The sum of the degrees of all vertices in the graph is the number of vertices multiplied by the degree of each vertex: \( \text{Sum of degrees} = n \times (n-1) \).
3. The Handshaking Lemma states that the sum of degrees is equal to twice the number of edges (\(2E\)).
\[ 2E = n(n-1) \] 4. To find the number of edges \(E\), we divide by 2:
\[ E = \frac{n(n-1)}{2} \] Step 4: Final Answer:
The number of edges in a complete graph with \(n\) vertices is \( \frac{n(n-1)}{2} \).