Доказать, что кубический двудольный граф не имеет мостов

[Shyroki]

Доказать, что кубический двудольный граф не имеет мостов.

Кубический граф - степени всех вершин равны 3.

Двудольный граф - граф, множество вершин которого можно разбить на две части так, что ребра соединяют только вершины из разных частей

(Двудольный граф (или биграф, или чётный граф) — это граф G(V,E), такой что множество V разбито на два непересекающихся подмножества V1 и V2, причём всякое ребро E инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). Множества V1 и V2 называются долями двудольного графа.)


Спасибо.

[Lion]

Советую посмотреть книгу Харари "Теория графов". Скорее всего, там это есть (и еще много чего интересного).

[Shyroki]

посмотрел у Харари - этой задачи нет.(может плохо смотрел?))). А сам доказать не могу
Может, кто-нибудь силен в графах(в теоретической части)?

[maxal]

а что есть мост?

[juna]

По-моему, все очевидно. Если есть мост, то при удалении этого ребра граф распадается на две компоненты связности. Но он двудольный (т.е. удаляя ребро мы удаляем его между множествами вершин $V_1$ и $V_2$), а с каждой вершиной инцидентны три ребра, т.е. не существует такого ребра при удалении которого граф сразу распадался на компоненты связности.

[Shyroki]

Всем спасибо.

Мне предложили еще одно решение, по-моему наиболее четкое:

sedated (14:11:46 29/12/2006)
на самом деле, если бы мост существовал, то убирая его, мы бы получили 2 связных двудольных графа.
взяв любой из них, заключаем, что у него в одной доле все врешины (пусть их m) степени 3, а в другой доле все, кроме одной, (пусть их k) степени 3. А у этой одной степень 2. Тепреь если считать количество рёбер по первой доле, то их 3*m, а по второй доле 3*k+2. Противоречие