Sách Another characterisation of planar graphs

Introduction
Several characterisations of planar graphs are known. (See [1–20].) We present a new one
based on the structure of the cocycle space of a graph.
Let G be a graph with vertex set V G and edge set EG. If S and T are disjoint sets
of vertices, we denote by [S, T ] the set of edges with one end in S and the other in T .
For any S ⊆ V G we write S = V G ư S, and we define ∂S = [S, S]. This set is called
a cocycle, the cocycle determined by S (or S). A bond is a minimal non-empty cocycle.
Thus a non-empty cocycle ∂S in a connected graph G is a bond if and only if G and
G are both connected. An isthmus is the unique member of a bond of cardinality 1.
Let A and B be distinct bonds in G. We say that two distinct edges of B ư A are bound
(to each other) by A with respect to B if they join vertices in the same two components
of G ư (A ∪ B).
Now let A1, A2, A3, B be distinct bonds in G, and let a ∈ B ư (A1 ∪ A2 ∪ A3). For
each i ∈ { 1, 2, 3} let Si be the set of edges bound to a by Ai with respect to B. We say
that a is tied by {A1, A2, A3} with respect to B if the following conditions hold: