Считаем рёбра

Рассмотрим момент перед поражением одного из игроков при правильной игре. Легко видеть, что граф должен состоять из двух компонент связности, каждая из которых представляет собой полный граф (иначе можно проводить ребра так, чтобы граф не стал связным). Пусть в одной из этих компонент вершин, тогда во второй Тогда ребер в этом графе

Ясно, что это число всегда нечетно. Тогда завершающий ход при правильной игре всегда принадлежит Васе. Значит, Петя всегда выиграет, играя как угодно, до того, как получатся две компоненты связности, а когда они получились, ему нужно проводить только ребра внутри них.