Question
Download Solution PDFThe largest number of faces in a simple connected maximal planar graph with 100 vertices is :
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFThe correct answer is option 3: 196
Key Points
- A maximal planar graph is a planar graph in which no more edges can be added without violating planarity.
- In a maximal planar graph with \( n \) vertices:
- Number of edges = \( 3n - 6 \)
- From Euler’s formula: \( V - E + F = 2 \)
- Given \( V = 100 \)
- So, edges \( E = 3 \cdot 100 - 6 = 294 \)
- Apply Euler's formula: \( 100 - 294 + F = 2 \Rightarrow F = 196 \)
Additional Information
- This maximum occurs because all faces in a maximal planar graph are triangles.
- Each triangle shares edges with others, making the total number of faces dependent on total edges and vertices.
Hence, the correct answer is: option 3: 196
Last updated on Jun 26, 2025
-> NIELIT Scientific Assistant admit card 2025 has been released.
-> NIELIT Scientific Assistant city intimation slip 2025 has been released at the official website.
-> NIELIT Scientific Assistant exam 2025 is scheduled to be conducted on June 28.
-> A total number of 113 revised vacancies have been announced for the post of Scientific Assistant in Computer Science (CS), Information Technology (IT), and Electronics & Communication (EC) streams.
-> Online application form, last date has been extended up to from 17th April 2025.
->The NIELT has revised the Essential Qualifications for the post of Scientific Assistant. Candidates must possess (M.Sc.)/ (MS)/ (MCA) / (B.E.)/ (B.Tech) in relevant disciplines.
-> The NIELIT Scientific Assistant 2025 Notification has been released by the National Institute of Electronics and Information Technology (NIELIT).