Question

Determine the density of a planar graph with 34 edges and 13 nodes.

(a) 22/21

(b) 12/23

(c) 328

(d) 576

I have been asked this question in a national level competition.

This question is from Planarity, Degree and Coloring of Graph in portion Graphs of Discrete Mathematics

Answer 1

The correct answer is (a) 22/21

The explanation: The density of a planar graph or network is described as the ratio of the number of edges(E) to the number of possible edges in a network with(N) nodes. So,  D = E − N + 1/ 2 N − 5. Hence, the required answer is: D=(34-13+1)/(2*13-5) = 22/21. A completely sparse planar graph has density 0 and a completely dense planar graph has degree 1.