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

78 Views Asked by At

Let $ G $ be a connected graph $ a \in E (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 $.

Demonstration. We will show $ a) \Rightarrow b) \Rightarrow c) \Rightarrow d) \Rightarrow a) $.

$ 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 exist $ u, \: v \in V (G) $ such that there is no $ uv- $path, since $ G $ is connected then every $ uv- $path contains $ a $.

$ c) \Rightarrow d) $: Suppose there exist $ 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 $ and $ v $ be the extremes of $ a $, with $ u \in U $ and $ v \in V $, thus $ u \neq v $, as by hypothesis every $ UV- $path contains $ a $ and $ a \notin E (G - \{a \}) $, then there is no $ uv- $path in $ G - \{a \} $, from where $ G - \{a \} $ is disconnected. Therefore, $ a $ is a bridge.

it's okay?