Question:
What is the maximum number of edges in an undirected simple planar graph with \(n \ge 3\) vertices?
\(n \ge 3\) शीर्षों वाले एक अप्रत्यक्ष सरल समतलीय (Planar) ग्राफ में किनारों की अधिकतम संख्या क्या हो सकती है?
Options:
- \(3n – 6\)
- \(2n – 4\)
- \(3n – 3\)
- \(n(n-1)/2\)
- \(3n – 6\)
- \(2n – 4\)
- \(3n – 3\)
- \(n(n-1)/2\)
Correct Answer: a)
Explanation:
By Euler’s planar formula \(V – E + F = 2\) and knowing that each face is bounded by at least 3 edges (\(2E \ge 3F\)), substituting yields \(E \le 3n – 6\).
यूलर के समतलीय सूत्र \(V – E + F = 2\) और \(2E \ge 3F\) से सिद्ध होता है कि किसी भी प्लेनर ग्राफ में अधिकतम किनारे \(3n – 6\) हो सकते हैं।