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.