Их ключевой момент заключается в том, что на графике нет циклов. Таким образом, каждый компонент вашего графа является деревом. См. Википедию для получения дополнительной информации: https://en.wikipedia.org/wiki/Tree_ (graph_theory)
Предположим в дальнейшем, что ваш граф имеет только один компонент и n узлов. Если в вашем графике несколько компонентов, просто возьмите самый большой и установите n на количество узлов этого компонента.
В худшем случае доставка письма происходит из листовой узел (внизу) до узла root (вверху) и затем вниз до другого листового узла. Этот путь имеет длину (n-1). Таким образом, эта доставка занимает (n-1) времени.
Другими словами: самый длинный путь в дереве с n узлами имеет длину n-1.