Докажите, что если в простом графе существуют разные пути между двумя вершинами, то граф имеет цикл

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

Однако, поскольку у нас есть разные пути между этими вершинами, мы можем выбрать вершину, в которую мы возвращаемся, и теперь у нас есть путь от этой вершины до исходной. Это создает цикл в графе, что противоречит нашему предположению.