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 :-)

3more comments