Discussion
Let G be a simple graph with degree of every vertex an even number \(\ge 2\). Then G is :
Answer: B
The keyed answer is disjoint union of cycles, read as an edge-disjoint union.
Veblen's theorem: a graph in which every vertex has even degree has its edge set partitioned into edge-disjoint cycles. Start at any vertex and walk along unused edges; even degrees mean the walk can always leave a vertex it enters, so it closes into a cycle; remove it and repeat.
The cycles need not be vertex-disjoint: two triangles sharing one vertex (degrees 2, 2, 4, 2, 2) is such a graph. That same graph shows the other options fail: it contains odd cycles, so it is not bipartite; it has no cycle through all five vertices, so it is not Hamiltonian; and the shared vertex is a cut vertex.
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