Cuts and Bonds

Bond: a minimal nonempty cut.

Let \(F=\delta(S)\) be a nontrivial cut in a connected graph. Then \(F\) is a bond if and only if \(G-F\) has exactly 2 components.

Proof.
\((\implies)\) Suppose \(G-F\) has more than 2 components and say two of them are in \(G[S]\). Let \(H\) be one of them. Then \(\delta_G(V(H))\subsetneq F\), contradicting minimality of \(F\).
\((\impliedby)\) Suppose \(F\) is not a bond. So, \( \delta (T) \subsetneq F\) where \(\delta(T)\neq \emptyset\). Then \(\exists e\in F-\delta(T)\) that joins two components. In \(G-\delta(T), \exists \) path from \(T\) to a vertex in \(e\) outside of \(T\), a contradiction.

Every cut is a disjoint union of bonds

Proof.
Suppose \(F\) is a cut. If \(|F|=0\), then it is disjoint union of no bonds. Assume \(F\neq \emptyset\). If \(F\) is a bond, then done. If \(F\) is not a bond, then there is a nonempty cut \(F'\subsetneq F\). Let \(F''=F-F'\). Then \(F''=F\Delta F'\). Then \(F''=F\Delta F'\). Since \(\delta (S) \Delta \delta(T)=\delta(S\Delta T)\) for any \(S,T\subseteq V(G)\), \(F''\) is a cut. Moreover, \(|F''|,|F'|\lt |F| \). It follows from the induction that \(F'\) and \(F''\) are disjoint union of bonds. Since \(F=F'\cup F''\) is disjoint, \(F\) is also a disjoint union of bonds.

Cylces

\(G\) has a cycle if \(\forall v\in V(G), \deg_G(v)\ge 2\ \)

Proof Idea. Take a maximal path in \(G\) and find a cycle.

Let \(G\) be a graph with >3 vertices. Then the followings are equivalent:

1. \(G\) is 2-connected
2. For any distict \(x,y\in V(G)\), there exists a cycle containing \(x,y\)
3. \(\delta(G)\ge 1\) and for any distict \(e,f\in E(G)\), there exists a cycle containing \(e,f\)

Proof Idea. Follows from k-fan lemma

The elements of \(\mathcal{C}(G) \) are precisely the even subgraphs of \(G\).

\(\dim\mathcal{C}(G) = |E(G)|-|V(G)|=k\) where \(k\) is the number of components in \(G\).

In a 2-connected plane graph, every face boundary is a cycle.

The cycle space of a 2-connected plane graph is spanned by the set of all facial cycles.

In a 3-conncted plane graph, all neighbours of a vertex \(v\) lie on a common cycle not using \(v\).

General

If \(G_1\) and \(G_2\) are even graphs, then \(G_1+G_2\) is also even.

Proof Idea. Think about the degree of each vertex.

Given \(G\), any even subgraphs of \(G\) are the elements in the cycle space \(\mathcal{C}(G)\).

Proof Idea. If \(E(H)=\emptyset\), then done. If not, \(d_v(H)\geq 2\) for all $v$ in nontrivial component of \(H\), then we can find a cycle \(C\) in it. Since \(C\) is even, \(H-C\) is even. Inductively find cycles in \(H-C\).

Note. It is easy to recognize that all the elements in the cycle space are even.

\(G\) is 2-connected if and only if \(G\) has an ear decomposition.

Proof Idea.
\((\implies)\) We can find cycles. Utilize cycles in \(G\).
\((\impliedby)\) For an ear decomposition \((G_0,G_1,\dots, G_k)\), we can show that \(G_i\) is 2-connected for each \(i\).

\(K_5\) and \(K_{3,3}\) are non-planar graphs.

Proof Idea. Assume they have planar embeddings, draw a contradiction using Jordan Curve Theorem.