Nice graph theory
Source: Russian TST 2016, Day 11 P3 (Group NG), P4 (Group A)
April 19, 2023
combinatoricsgraph theory
Problem Statement
A simple graph has vertices and less than edges. Prove that its vertices can be divided into two non-empty groups so that each vertex has at most one neighbor in the group it doesn't belong to.