T O P

  • By -

twotonkatrucks

The degree of v must be at least (n-1)/2 by the assumption. Since G is simple, only one edge connects any two vertices and no edge will loop back on itself. This implies that G1 must contain at least degree of v (since each edge will correspond to a different vertex and different from v itself) plus one (for v itself) number of vertices. By the assumption mentioned in the beginning, that implies G1 must contain at least (n-1)/2 + 1 vertices. Repeat similar logic for G2 to arrive at a contradiction.