The Connectivities of Trunk Graphs of \(2\)-Connected Graphs

Let \(G\) be a connected graph and \(\mathcal{V}^*\) the set of all spanning trees except stars in \(G\). An edge in a spanning tree is called `inner’ if the edge is not incident to endvertices. Define an adjacency relation in \(\mathcal{V}^*\) as follows: two spanning trees \(t_1\) and \(t_2 \in \mathcal{V}^*\) are called to be adjacent if there exist inner edges \(e_i \in E(t_i)\) such that \(t_1 – e_1 = t_2 – e_2\). The resultant graph is a subgraph of the tree graph, and we call it simply a trunk graph. The purpose of this paper is to show that if a \(2\)-connected graph with at least five vertices is \(k\)-edge connected, then its trunk graph is \((k-1)\)-connected.