Sách A note on circuit graphs

We only consider finite graphs without loops or multiple edges. For a graph G, we use
V (G) and E(G) to denote the vertex set and edge set of G, respectively. A k-walk in G
is a walk passing through every vertex of G at least once and at most k times. A circuit
graph (G, C) is a 2-connected plane graph G with outer cycle C such that for each 2-cut
S in G, every component of G ư S contains a vertex of C. It is immediate that every
3-connected planar graph G is a circuit graph (we may choose C to be any facial cycle of
G).
In 1994, Gao and Richter [3] proved that every circuit graph contains a closed 2-
walk. The existence of such a walk in every 3-connected planar graph was conjectured by
Jackson and Wormald [5]. Gao, Richter, and Yu [4] extended this result by showing that
every 3-connected planar graph has a closed 2-walk such that any vertex visited twice is
in a vertex cut of size 3. (It is easy to see that this also implies Tutte’s theorem [7] that
every 4-connected planar graph is Hamiltonian.) The main objective of this note is to
present a short proof of Gao and Richter’s result.