Let G be a loop-free undirected graph with n vertices. If G has 56 edges and…
Let G be a loop-free undirected graph with n vertices. If G has 56 edges and G^C (the complement of G) has 80 edges, then what is the value of n?
Answer: 17 — Number of edges in G plus the number of edges in G^C (the complement of G) equals n(n - 1)/2. 56 + 80 = n(n - 1)/2 136 = n(n - 1)/2 272 = n(n - 1) n^2 - n -…
Attempted by 78 students.
Show answer & explanation
Correct answer: 17
Number of edges in G plus the number of edges in G^C (the complement of G) equals n(n - 1)/2.
56 + 80 = n(n - 1)/2
136 = n(n - 1)/2
272 = n(n - 1)
n^2 - n - 272 = 0
Solve the quadratic: n = (1 + sqrt(1 + 4·272))/2 = (1 + sqrt(1089))/2 = (1 + 33)/2 = 17.
Loading lesson…