graph has no bridge iff a spanning subgraph of the graph is the support of a flow

30 Views Asked by At

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$.

Let $\mathcal{O}$ be an orientation of the edges of $G$. For every $v\in V$, let $v^+$ and $v^-$ be the set of edges pointing out of and the set of edges pointing towards $v$, respectively, with respect to $\mathcal{O}$. Let $K$ be a field of characteristic $0$ and let $$W=\left\{f:E\rightarrow K: \forall v\in V \displaystyle \sum_{e\in v^+}f(e)=\sum_{e\in v^-}f(e) \right\}.$$

We call the elements of $W$ $\textit{flows}$. We can view $W$ as a vector space. Suppose $|E|=m$. Then $f\in W$ is an $m$-tuple (so $f=(f(e_1), \ldots ,f(e_m)))$. The $\textit{support}$ of $f\in W$ is $\text{supp}(f)=\left\{i: f(e_i)\neq 0 \right\}$.

I am trying to figure out a hint given in a book: "a spanning subgraph of $G$ is the support of a flow iff it has no bridge". If someone could intuitively explain this, I would appreciate it! Thank you :-)