Current location - Training Enrollment Network - Mathematics courses - Proving non-Euler discrete mathematical problems with bridges
Proving non-Euler discrete mathematical problems with bridges
Reduction to absurdity. Let graph G be an Euler graph. Using a property of simple loop, let C be any simple loop and E be any edge on C, then c-e is still connected. Write this attribute down as *

Because G is an Euler diagram, there is an Euler path. Let C be one of Euler paths, then any edge in G is on C. Therefore, e∈E(G), G' = G-E = C-E. According to *, G' is still connected, so according to the definition of bridge, E is not a bridge in G. The arbitrariness of E proves that there is no bridge in G. Therefore, the assumption is wrong, Figure.