Edge-disjoint Spanning Trees And The Number Of Maximum State Circles Of A Graph

A link L is the disjoint union of embeddings of circles S1,S into the Euclidean 3-space E3.A link diagram D（G）is a planar representation of a link L.Given a nontrivial connected plane graph G,we can construct an alternating link diagram D（G）via the medial construction.Motivated by the connection with the genus of unoriented alternating links,Jin et al.[9]introduced the number of maximum state circles of a plane graph G,denoted by S_max（G）,and proved that S_max（G）= max {e（Ⅱ）+ 2c（Ⅱ）-v（Ⅱ）| H is a H（?）G spanning subgraph of G},wheree（H）,c（H）and v（H）denote the size,the number of connected components and the order of H,respectively.In this paper,we show that S_max（G）for any（not necessarily planar）graph G can be achieved by the spanning subgraph H of G whose each connected component is a maximal subgraph of G with two edge-disjoint spanning trees.Such a spanning subgraph is proved to be unique and we then present a polynomial-time algorithm to find such a spanning subgraph for any graph G.