Discussion
Which of the following statements is true for a graph G ?
Answer: B
The true statement is that every regular graph of even degree has a 2-factor.
This is Petersen's 2-factor theorem (1891): every \(2k\)-regular graph has a 2-factor, a spanning subgraph in which every vertex has degree 2. Indeed its edges can be split into \(k\) edge-disjoint 2-factors. The proof takes an Eulerian circuit of each component, orients it, and applies Hall's theorem to the resulting bipartite graph.
The others fail. A graph with an odd number of vertices has no perfect matching (A). A bipartite graph with no pendant vertex need not have a 2-factor; \(K_{2,3}\) has none, since its two sides differ in size (C). And the line graph of a regular graph can have an odd number of vertices, e.g. that of \(K_{3}\) is \(K_{3}\), with no 1-factor (D).
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