Пусть в ориентированном графе G исходящая степень каждой вершины равна входящей. Если стереть ориентацию на рёбрах, то получится связный неориентированный граф H. Докажите, что ориентированный граф G сильно связен.

Предположим, что такой граф разбился на несколько компонент сильной связности. Рассмотрим две компоненты M и K. Т.к. по условию неориентированный граф связен, то есть хотя бы одно ребро, ведущее из M в K (или наоборот, но не умаляя общности возьмем такой вариант). Докажем, что есть ребро, ведущее из K в M. Предположим, что такого ребра нет. Пусть сумма входящих степеней вершин в M равна x. Тогда сумма исходящих степеней вершин в M равна хотя бы x + 1(все входящие ребра в вершины в M + хотя бы 1 ребро, ведущее из M в K). Но тогда получим, что сумма исходящих и входящих степеней различны, что противоречит условию, что исходящие и входящие степени для каждой вершины равны (тогда и сумма степеней исходящих ребер и входящих равны для любого количества вершин). Тогда существует ребро из K в M ⇒ M и K – одна компонента сильной связности ⇒ Граф G сильно связен