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.

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.

The followings are equivalent:

1. \(G\) is 2-connected.
2. For any distinct \(v,w\in V(G)\), there exists a cylce containing \(v,w\).
3. For any distinct \(e,f\in E(G)\), there exists a cycle containing \(e,f\).

Proof Idea. Directly follows from the fan lemma.

\(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.