Spanning trees in 3 regular graphs.

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

-
What do "clip" and "half edges" mean? –  Alon Amit Sep 16 '11 at 1:57
Sorry, I'm using the language I'm used to using with my colleague Eran Makover. What I mean by "clip" is to cut the edge, of course when you cut enough edges you get a tree. If you then embed the tree in the plane, each edge which was cut shows up in two places, and those we consider identified. 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. Does that make sense? –  Jeff McGowan Sep 16 '11 at 2:13
So are the half edges just the leaves of the tree? –  Daniel Mansfield Sep 16 '11 at 2:27
Also, I'm sure you can construct an example of 3-regular graphs which has many "long" paths and many "short" ones. It would look something like a big Y. Perhaps more detail about what is considered long and short would be helpful. Or, if you didn't like the big "Y", here's another example t1.gstatic.com/… –  Daniel Mansfield Sep 16 '11 at 2:37
@Jeff McGowan, it may help if you describe an explicit example of a cubic graph and the process of "clipping" it to a spanning tree in your question. You might also be able to explain more what you're looking for in 1) and 2) with an example at hand. –  j.c. Sep 16 '11 at 2:56

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.

-

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.

-
Martin, Yes, you would definitely need assumptions to get either thing to always be true, we are not expecting that. Our arguments are probabilistic, in that we look at what happens as the number of vertices goes to infinity, in which case the probability of certain things happening goes to 1. For example, as you probably know, the probability that there is a Hamiltonian cycle in a 3 regular graph goes to 1 as the size goes to infinity. Your construction is very nice, it's giving me some ideas about how to imagine taking a given spanning tree and rearranging into another tree...Thanks! –  Jeff McGowan Sep 19 '11 at 14:04