Question

If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is  ___________

(a) (n*n-n-2*m)/2

(b) (n*n+n+2*m)/2

(c) (n*n-n-2*m)/2

(d) (n*n-n+2*m)/2

My query is from Graph topic in section Graph of Data Structures & Algorithms I

This question was addressed to me in my homework.

Answer 1

Right choice is (a) (n*n-n-2*m)/2

For explanation: The union of G and G’ would be a complete graph so, the number of  edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).