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: Another characterisation of planar graphs. | Another characterisation of planar graphs C. H. C. Little Massey University Palmerston North New Zealand G. Sanjith Indian Institute of Technology Madras Chennai India theemergingmind@ Submitted Sep 13 2009 Accepted Mar 1 2010 Published Mar 8 2010 Mathematics Subject Classification 05C10 Abstract A new characterisation of planar graphs is presented. It concerns the structure of the cocycle space of a graph and is motivated by consideration of the dual of an elementary property enjoyed by sets of circuits in any graph. 1 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 VG 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 c VG we write S VG S and we define dS 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 dS in a connected graph G is a bond if and only if G S and G S 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 u B . Now let A1 A2 A3 B be distinct bonds in G and let a E B Al u A2 u A3 . For each i E 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 Supported by KVPY THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N15 1 V ữ v4 Figure 1 K5 1. for each i there is a component of G Aị u B that contains an end of a and an end of an edge of Ai n B 2. each of S1 S2 S3 contains an edge that is in neither of the other two. Edge a is tied if there exist bonds A1 A2 A3 B such that a is tied by Al A2 A3 with respect to B . The