Spanning trees in 3 regular graphs.

Question

Suppose I have a 3 regular graph, and I cut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. The background is that what we are really looking at is Riemann surfaces, and the graph corresponds to a triangulation, and the tree corresponds to a fundamental domain, where the "half edges" are identified sides - think Belyi and Grothendieck.

As an example, consider the usual two holed torus, which can be given by identifying the edges of an octagon in pairs. Triangulate the octagon, put a vertex in every triangle, and connect neighboring vertices with an edge. Include vertices which have a paired external side, so you get a 3 regular graph. Now imagine reversing direction, so you start with a random 3 regular graph, and you cut edges until you have a tree, put a triangle at each vertex, and you get an octagon with paired sides, thus a two holed torus (depending on the pairings, you might of course get a torus or a sphere). Now imagine a much bigger graph, but the same idea. Start with a random graph, cut edges, and generate a fundamental domain (note again that it is unclear what the genus of the related surface will actually be, but ignore that for now). The hope would be that one could get the "usual" domain $aba^{−1}b^{−1}cdc^{−1}d^{−1}\ldots$ with sides identified in alternating pairs, but of course this is not usually possible while respecting the triangulation. So the question is can one somehow get something with all the paired leaves roughly the same distance or with one set far apart and the others close. The question is not exactly well formed, but I think you can think of two basic possibilities - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

@jc's suggestion, I moved the clarifications up here, duh :-)

Answer 1

I cannot see a clear question here, and so this is certainly not an answer. But perhaps you could clarify the question via an explicit example.

As I understand it, if you restricted attention to triangulated surfaces homemorphic to a sphere (which I know is not your interest), your cutting would produce what is called a net, or an unfolding. You are looking at the dual of the net, and want either bushy trees or Hamiltonian paths.

There are exactly 43,380 distinct nets for the icosahedron. Left below is an unfolding with a bushy dual tree; on the right an unfolding whose dual is a Hamiltonian path.
     
The only points I want to make with this example are: (a) There are many spanning trees (exponential in the number of triangles), and (b) among them you can probably find spanning trees of any desired shape.

Answer 2

I hope that I understand your question well. (Say that you have leaves $a^+$ and $a^-$ obtained by cutting an edge $a$ and similarly $b^+$ and $b^-$ by cutting an edge $b$. My understanding is that you consider only $a^+a^-$ path, $b^+b^-$ path, but not, e.g., $a^+b^+$ path.)

If the graph is given (say by an "enemy") you may not succed with any of your goals.

First, I will show a construction where you cannot have one long path and many short ones.

1. Start with a vertex of degree 3 attached to three leaves.
2. Replace every leaf with another vertex of degree three (now it is attached to two leaves and one vertex of the original graph).
3. Repeat this step until you obtain a tree $T$ with $3\cdot2^k$ leaves and $3\cdot 2^k - 2$ vertices of degree 3.
4. Replace every leaf of $T$ with the following graph: $$V(H) = \{1,2,3,4,5\};$$ $$E(H) = \{12, 23, 34, 45, 51, 24, 35\}.$$ More precisely, identify the vertex number 1 with the leaf. Thus you obtain a 3-regular graph.

Now If you want to cut the edges of the resulting graph in order to obtain a spanning tree, you can only cut edges inside copies of $H$. Thus all paths are very short and you do not achieve goal 1).

In addition you may play a bit with steps 1., 2., 3. in the construction; depending on your choice, you may more or less force the lengths of paths. For instance, start with cycle to on $j$ vertices. Attach a leaf to every vertex and then proceed with the step 4. Then you have to have one path with length $j$ and many short paths weakly disallowing case 2). However, you can also start with many cycles connected with edges in some tree-like structure. Then you even disallow 1) and 2) at once (depending what does "most" in your question mean).

Perhaps some assumptions should be put on the graphs.