Discussion
G is a complete graph with V-vertices and E-edges. Then which of the following is false ?
Answer: C
The false statement is G cannot be planar for any value of V and E.
The complete graphs \(K_{1}\) to \(K_{4}\) are all planar: \(K_{4}\) can be drawn as a triangle with a vertex in the middle joined to the three corners, with no edges crossing. Only from \(K_{5}\) onwards is a complete graph non-planar, by Kuratowski's theorem, so the statement fails for small V.
The other statements are true. A complete graph on V vertices needs exactly V colours, since every vertex is adjacent to every other, so it is V-colourable. Each pair of vertices is joined by one edge, giving \(E = V(V-1)/2\). And every vertex is adjacent to every other, so the graph is always connected.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development