Рассмотрим максимальное паросочетание, то есть максимально возможное число 𝑚 такое, что 𝑚 дорог оканчиваются в 2𝑚 различных городах. Очевидно, что 𝑚 ≥ 1. Предположим, что 𝑚 ≤ 5. Тогда в паросочетание не вошли 20 − 2𝑚 городов. Из них каждый с кем-то соединён, но никакие не соединены между собой, так как в противном случае можно увеличить паросочетание ещё на одну пару. Для каждого из 20 − 2𝑚 городов рассмотрим его соединение дорогой с кем-то из 2𝑚 участников паросочетания. Тогда все эти дороги будут попарно различными, и к ним добавятся ещё 𝑚 дорог между городами. Всего получится 20 − 𝑚 дорог, что не должно превосходить 14, откуда 𝑚 ≥ 6 — противоречие.