Контрпример — утверждение неверно.
Контрпримеры:
- Пусть $G$ — путь из четырёх вершин (три ребра). Все три ребра — мосты, их число равно $3$. Но граф двудольный, поэтому одна двоичная разметка (разбиение на две доли) делает концы всех рёбер разными: достаточно одного разбиения. То есть минимальное число разбиений равно $1\ne 3$.
- Треугольник $C_3$: мостов нет (число мостов $0$), но ни одно одноразбиение не пересекает все три ребра (любое разбиение разделяет одну вершину от двух и режет ровно $2$ ребра), поэтому требуется как минимум $2$ разбиения; значит минимум $2\ne 0$.
Обобщённая корректная формулировка и доказательство
Рассмотрим задачу: найти минимальное число двоичных разбиений вершин (каждое разбиение — бит), таких что для каждого ребра есть хотя бы одно разбиение, разделяющее его концы. Если у нас $t$ таких разбиений, каждому вершинному набору соответствует битовая строка длины $t$. Условие «для каждого ребра концы различаются в какой‑то бит» эквивалентно требованию, что смежные вершины имеют разные бит‑строки, т.е. все смежные вершины получают разные «цвета». Значит эти бит‑строки задают правильную раскраску вершин в не более чем $2^t$ цветов. Обратно, любая раскраска в $k$ цветов даёт $t=\lceil {\log }_{2}k\rceil$ битов (достаточно сопоставить каждому цвету уникальную битовую строку длины $t$). Следовательно минимальное $t$ равно
$$t=\lceil {\log }_2\chi (G)\rceil ,$$ где $\chi (G)$ — хроматическое число графа $G$.
Выводы и связь с алгоритмами и сложностью
- Количество мостов в графе не определяет это минимальное $t$; приведённые контрпримеры это показывают.
- Нахождение мостов (алгоритм Тарьяна / DFS) делается за $O(n+m)$, но эти сведения не дают значения $t$.
- Поскольку вычисление $\chi (G)$ — NP‑полная задача, вычисление
$t=\lceil {\log }_2\chi (G)\rceil$ также NP‑трудно. Для частных случаев есть простые ответы: если $G$ двудольный и содержит ребро, $t=1$; для полного графа $K_n$ имеем $t=\lceil {\log }_{2}n\rceil$.
Кратко: утверждение ложно; правильная характеристика — минимальное число разбиений равно $\lceil {\log }_2\chi (G)\rceil$; вычисление этого числа в общем случае NP‑трудно, тогда как поиск мостов полиномиален.