A graph G and its complement Ḡ have 8 and 7 edges respectively. Then the…
A graph G and its complement Ḡ have 8 and 7 edges respectively. Then the number of vertices in G is
Answer: A. 6 — Let the number of vertices in graph G be n. The total number of possible edges in a complete graph with n vertices is For any graph G and its complement Ḡ,…
- A.
6
- B.
5
- C.
8
- D.
none of these
Attempted by 134 students.
Show answer & explanation
Correct answer: A
Let the number of vertices in graph G be n.
The total number of possible edges in a complete graph with n vertices is
For any graph G and its complement Ḡ, the sum of their edges equals the total number of edges in the complete graph:
Given |E(G)| = 8 and |E(Ḡ)| = 7, substitute into the equation:
Simplify:
Multiply both sides by 2:
Rearrange into a quadratic equation:
Factor the quadratic:
Solve for n:
Since the number of vertices cannot be negative, n = 6.