A Combinatorial Decomposition Theory

<jats:p>Given a finite undirected graph<jats:italic>G</jats:italic>and<jats:italic>A</jats:italic>⊆<jats:italic>E(G)</jats:italic>,<jats:italic>G(A)</jats:italic>denotes the subgraph of<jats:italic>G</jats:italic>having edge-set<jats:italic>A</jats:italic>and having no isolated vertices. For a partition {<jats:italic>E<jats:sub>1</jats:sub>, E<jats:sub>2</jats:sub>}</jats:italic>of<jats:italic>E</jats:italic>(<jats:italic>G</jats:italic>),<jats:italic>W(G; E<jats:sub>1</jats:sub>)</jats:italic>denotes the set<jats:italic>V(G(E<jats:sub>1</jats:sub>))</jats:italic>⋂<jats:italic>V</jats:italic>(<jats:italic>G</jats:italic>(<jats:italic>E</jats:italic><jats:sub>2</jats:sub>)). We say that<jats:italic>G</jats:italic>is<jats:italic>non-separable</jats:italic>if it is connected and for every proper, non-empty subset<jats:italic>A</jats:italic>of<jats:italic>E(G)</jats:italic>, we have |<jats:italic>W</jats:italic>(<jats:italic>G</jats:italic>;<jats:italic>A</jats:italic>)| ≧ 2. A<jats:italic>split</jats:italic>of a non-separable graph<jats:italic>G</jats:italic>is a partition {<jats:italic>E<jats:sub>1</jats:sub>, E<jats:sub>2</jats:sub></jats:italic>} of<jats:italic>E(G)</jats:italic>such that</jats:p><jats:p>|<jats:italic>E<jats:sub>1</jats:sub></jats:italic>| ≧ 2 ≧ |E<jats:sub>2</jats:sub>| and |<jats:italic>W(G; E<jats:sub>1</jats:sub>)</jats:italic>| = 2.</jats:p><jats:p>Where {<jats:italic>E<jats:sub>1</jats:sub>, E<jats:sub>2</jats:sub></jats:italic>} is a split of<jats:italic>G, W(G; E<jats:sub>2</jats:sub>)</jats:italic>= {<jats:italic>u, v</jats:italic>}, and<jats:italic>e</jats:italic>is an element not in<jats:italic>E(G),</jats:italic>we form graphs<jats:italic>G<jats:sub>i</jats:sub></jats:italic><jats:italic>i</jats:italic>= 1 and 2, by adding<jats:italic>e</jats:italic>to<jats:italic>G(E<jats:sub>i</jats:sub>)</jats:italic>as an edge joining<jats:italic>u</jats:italic>to<jats:italic>v.</jats:italic></jats:p>