Characterizing Minimally 3-Connected Graphs
摘要
In 1986 Dawes gave a necessary and sufficient characterization for the construction of minimally 3-connected graphs starting with \(K_4\) . Two distinct edges e and f are bridged if they are subdivided by vertices x and y, respectively, forming paths of length 2, and x and y are joined by an edge. A vertex w and an edge e are bridged if e is subdivided by vertex x, and w and x are joined. A triad is added when a new vertex is introduced and joined to three distinct vertices in the graph. Using these three operations, and what he called compatible sets, Dawes gave a necessary and sufficient condition for the construction of minimally 3-connected graphs. We translate Dawes’ operations to edge additions and vertex splits, and give a new proof of necessity.