2) не так. максимальное паросочетание по мощности равно минимальному вершинному покрытию, а максимальное независимое множество — это инверсия минимального вершинного покрытия.

После этой задачи осталось много злости. Два дня пихал разные алгоритмы на разных языках и все таймило. Почему авторы не делают нормального запаса в тайм лимите?

Про первый пункт все ясно — если две пушки друг друга бьют, у них различная четность, например, величины x/4%2. Значит, можно разбить на две доли по этой четности.

Про паросочетание я умею доказывать, сводя к 2-SAT и показывая, что этот 2-SAT разрешим тогда и только тогда, когда паросочетание максимальное (то есть нет увеличивающих цепей). Сведение такое. Пусть есть произвольное паросочетание (максимальное или нет), такое, что нет ребер между неспаренными вершинами. Возьмем в наше потенциально независимое множество все неспаренные вершины и по одной вершины из каждой пары. Как выбирать, какую вершину из пары взять? Построить набор ограничений вида "если взяли эту вершину в этой паре, обязаны взять ту вершину в той паре". Из каждого ребра между спаренными вершинами получаются два таких ограничения. Еще из каждого ребра между спаренной и неспаренной вершиной получается простое ограничение вида "в этой паре берем эту вершину". Теперь можно посмотреть на структуру получившегося 2-SAT и понять, как противоречие в ограничениях соответствует увеличивающей цепи в графе.

2.1. В двудольном графе мощность максимального паросочетания совпадает с мощностью минимального вершинного покрытия.

Доказательство есть, например, здесь. Можно взять по одной вершине из каждого ребра паросочетания и двигать их, наращивая количество покрытых рёбер, но при строгом описании получится что-то похожее.

2.2. Мощность минимального вершинного покрытия (а значит, и максимального паросочетания) + мощность максимального независимого множества в произвольном неориентированном графе = количество вершин.

Нетрудно понять, что вершинное покрытие всегда является дополнением независимого множества (и наоборот). Так как сумма их мощностей постоянна и равна числу вершин, мин. вершинному покрытию соответствует дополнение — макс. независимое множество.