Question

The maximum number of edges in a 8-node undirected graph without self loops is ____________

(a) 45

(b) 61

(c) 28

(d) 17

I have been asked this question by my school principal while I was bunking the class.

This intriguing question comes from Complete and Connected Graphs topic in section Graphs of Discrete Mathematics

Answer 1

The correct answer is (c) 28

Easy explanation: In a graph of n vertices we can draw an edge from a vertex to n-1 vertex we will do it for n vertices and so total number of edges is n*(n-1). Now each edge is counted twice so the required maximum number of edges is n*(n-1)/2. Hence, 8*(8-1)/2 = 28 edges.