grafy, d-regularny, most

[danielek12201220]

wykaz ze jesli graf \(\displaystyle{ G=(V,E)}\) dwudzielny jest \(\displaystyle{ d}\)-regularny, to nie istnieje w nim most.

-- 27 mar 2017, o 22:29 --

moja idea dowodu jest taka ze zalozmy ze istnieje ten most. a wiec usunmy jedna krawedz laczaca dwa wierzcholki tak, aby powstaly dwie spojne skladowe. Jednak gdy usuniemy ta jedna krawedz pomiedzy tymi dwoma wierzcholkami to zostanie na pewno jeszcze jakas poniewaz \(\displaystyle{ d\ge 2}\) z zalozenia, a wiec nadal sa one polaczone , a wiec dochodzimy do sprzecznosci a wiec hipoteza jest sprzeczna a wiec teza prawdziwa wiec nie istnieje most w takim grafie. czy ktos cos ?

[Downonmyluck]

Weźmy graf \(\displaystyle{ G-{uv}}\), gdzie \(\displaystyle{ uv}\) jest mostem i rozważmy jedną ze spójnych składowych \(\displaystyle{ H}\) tego grafu taką, że \(\displaystyle{ u \in V(H)}\) . \(\displaystyle{ H}\) jest grafem dwudzielnym, wobec tego \(\displaystyle{ V(H) = (V(H) \cap X) \cup (V(H) \cap Y)}\) (gdzie \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są klasami dwudzielności grafu \(\displaystyle{ G}\)) musi zatem zachodzić zależność
\(\displaystyle{ d \cdot (\left| V(H) \cap X\right| - 1) + d-1 = d(\left| V(H) \cap Y\right|)}\). Otrzymujemy

\(\displaystyle{ \frac{d-1}{d} = (\left| V(H) \cap Y\right| - \left| V(H) \cap X\right| +1)}\), a to jest sprzeczność, bo dla \(\displaystyle{ d \ge 2}\) liczba \(\displaystyle{ \frac{d-1}{d}}\) jest niecałkowita.