Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A note on circuit graphs Qing Cui. | A note on circuit graphs Qing Cui Department of Mathematics Nanjing University of Aeronautics and Astronautics Nanjing 210016 P. R. China cui@ Submitted Oct 12 2009 Accepted Jan 22 2010 Published Jan 31 2010 Mathematics Subject Classifications 05C38 05C40 Abstract We give a short proof of Gao and Richter s theorem that every circuit graph contains a closed walk visiting each vertex once or twice. 1 Introduction 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. Theorem 1 Let G C be a circuit graph and let u v G V C . Then there is a closed 2-walk W in G visiting u and v exactly once and traversing every edge of C exactly once. We conclude this section with some notation and terminology. A plane chain of blocks is a graph embedded in the plane with blocks B1 B2 . Bk such that for each i 1 . k 1 Bi and Bi l have a vertex in common no two of which are the same THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N10 1 and for each j 1 2 . k ui j Bị is in
