Discussion
Let G be a simple graph having no isolated vertex and having no vertex induced subgraph with exactly two edges. Then :
Answer: C
G is complete.
Suppose two vertices \(u, w\) are not adjacent. If they had a common neighbour \(v\), the set {u, v, w} would induce a subgraph with exactly two edges. So within a connected component, any non-adjacent pair would lead along a path to such a forbidden triple; hence each component is a complete graph.
If there were two components, each has an edge (no isolated vertices), and an edge from each would induce a subgraph on four vertices with exactly two edges. So G is a single complete graph.
A complete graph need not be planar (\(K_{5}\)), is not self-complementary (its complement has no edges), and is a tree only when it has two vertices, so A, B and D do not hold in general.
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