Для доказательства данного утверждения необходимо доказать его двустороннюю импликацию, то есть разбить его на два логических утверждения и доказать их обратные импликации.
Пусть утверждение A гласит: “Если вершина х является точкой сочленения графа G, то существуют отличные от х вершины у и 2, такие, что х содержится в каждом пути из у в 2”.
Пусть утверждение B гласит: “Если существуют отличные от х вершины у и 2, такие, что х содержится в каждом пути из у в 2, то вершина х является точкой сочленения графа G”.
Пусть для наглядности вершины у и 2 обозначаются как u и v соответственно.
1. Докажем, что A => B (то есть если вершина х является точкой сочленения, то существуют вершины u и v, такие что х лежит на всех путях из u в v).
Пусть х является точкой сочленения графа G. Тогда удаление вершины х должно приводить к появлению новых компонент связности. Для каждой компоненты связности C существует путь из u в v, где u и v – вершины, не входящие в C. Таким образом, х содержится в каждом пути из u в v.
2. Докажем, что B => A (то есть если существуют вершины u и v, такие что х лежит на всех путях из u в v, то вершина х является точкой сочленения графа G).
Пусть существуют вершины u и v, такие что х лежит на всех путях из u в v. Рассмотрим случай, когда удалим вершину х. Если существует компонента связности C, в которую входят вершины u и v, то путь из u в v все еще существует, так как в него не входит вершина х. Если таких компонент связности больше одной, то вершина х является точкой сочленения.
Таким образом, мы доказали обратные импликации и тем самым доказали, что вершина х является точкой сочленения графа G тогда и только тогда, когда существуют вершины u и v, такие что х лежит на всех путях из u в v.