Известно, что в ориентированном графе на ⩾ 2 вершинах из любой вершины в любую другую идёт ровно один простой путь. Верно ли, что исходящие степени вершин в этом графе равны 1?

Рассмотрим ориентированный граф (такой чтобы можно было из любой вершины достичь любую другую) с вершинами 0, 1, 2 и ребрами 0 -> 1, 1 -> 0, 0 -> 2, 2 -> 0.
Для любого пути $ 0 -> v_1 -> . . . -> v_n -> 1 $ при n> 0 имеем $ v_n = 0 $, поскольку 0 -> 1 есть единственное ребро с концом 1. Следовательно, единственный простой путь из 0 в 1 есть 0 -> 1.
Для любого пути $ 1 -> v_1 -> . . .-> v_n -> 2 $ при n > 1 аналогичным образом имеем $ v_n = 0 $ и $ v_1 = 0 $. Следовательно, в простом пути из 1 в 2 обязательно k = 1, а единственный таковой есть путь 1 -> 0 -> 2. Симметричные пары вершин рассматриваются так же.
Итак, ориентированный граф удовлетворяет условию задачи, однако в нем $ deg(v_0)\ = 2 $. Противоречие.