Let $ G $ be a connected graph $ a \in A (G) $, they are equivalent:

Question

Let $ G $ be a connected graph $ a \in A (G) $, they are equivalent:

a) $ a $ is a bridge of $ G $.

b) $ a $ does not belong to a cycle.

c) There are $ u, v \in V (G) $ such that every $ uv- $ path contains $ a $.

d) There is a $\{U, V \}$ partition of $ V (G) $ such that every $UV-$path contains $ a $.

The usual thing is to show that $a)\Rightarrow b)\Rightarrow c)\Rightarrow d)\Rightarrow a)$. I have the following:

$a) \Rightarrow b)$: Suppose $ a $ is a $ G $ bridge and is on a $ G $ cycle. By eliminating $ a $, we know that there is a path between two vertices of $ a $. But this is contradicted by the definition of a bridge. Therefore, $ a $ is not in a cycle.

$b) \Rightarrow c)$: Since $ a $ is not in a cycle, $ a $ is a bridge, so $ G - \{a \} $ is disconnected. Thus there exists $ u, v \in V (G - \{a \}) $ such that there is no $ uv- $ path, since $ G $ is connected then every $ uv- $ path contains $ a $ .

Answer 1

$ a) \Rightarrow b) $: Suppose edge $ a $ is a bridge, but it is in a cycle. Consider the endpoints $ x $ and $ y $ from $ to $. Let's remove $ a $ from $ G $. Suppose $ x $ and $ y $ are disconnected, since $ a $ is a bridge. But, $ a $ is in a loop, so $ x $ can be reached from $ y $ (and vice versa) by following the loop in the opposite direction from $ to $; therefore, $ x $ and $ y $ do not disconnect when $ a $ is removed, a contradiction since $ a $ is a bridge. Therefore, $ a $ is not in a cycle.

$ b) \Rightarrow c) $: Let's consider again the edge $ a = xy $. Since $ a $ is not in a cycle, there must be no other path connecting $ x $ and $ y $, otherwise $ a $ would be in a cycle. In this case, removing $ a $ from $ G $ should disconnect $ x $ y $ y $ in $ G $; that is, $ G - \{a \} $ is disconnected and therefore there are $ u, \: v \in V (G) $ such that there is no $ uv- $path, as $ G $ is connected then all $ uv- $path contains $ a $.

Answer 2

$ c) \Rightarrow d) $: Suppose there exists $ u, \: v \in V (G) $ such that every $ uv- $ path contains $ a $, then in $ G - \{a \} $ there is no $ uv- $path. Therefore $ G - \{a \} $ is not connected. Let $ G_1, \: \ldots, \: G_l $ be the connected components of $ G - \{a \} $, by choosing $ u $ and $ v $, they must belong to different components, without losing generality Suppose $ u \in V (G_1) $ and $ v \in V (G_2) $. Let's define $ U = V (G_1) $ and $ V = \cup_ {i = 2} ^ {l} V (G_i) $.

Assertion: $ \{U, \: V \} $ is a partition of $ V (G) $.

i) $ U \neq \emptyset $ then $ u \in U $.

ii) $ V \neq \emptyset $ since $ v \in V $.

iii) $ U \cap V = \emptyset $ by the definition of $ U $ and $ V $.

iv) $ U \cup V = V (G) $ by the definition of $ U $ and $ V $.

$ d) \Rightarrow a) $: Let $ u \in U $ y $ v \in V $, $ a = x and $ thus $ u \neq v \neq x \neq y $, as by hypothesis all $ UV- $path contains $ a $ and $ a \notin A (G - \{a \}) $, so there is no $ uv- $ path in $ G - \{a \} $, hence $ G - \{a \} $ is disconnected. Therefore, $ a $ is a bridge.