Average branching factor of an undirected graph

Question

I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $n$ nodes, an average branching factor $b_f$ and $n_l$ leaf nodes, these three variables are related as follow:

$$b_f = \frac{e}{n-n_l} \Rightarrow n_l = n - \frac{e}{b_f}$$

where $e = n - 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $n$ nodes and $e = n - 1 + k$ edges (or with $k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $k$ edges are the one being ignored from the graph.

Is there any known property of graph's spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $$n_l <= |\{n_{e^1}\}| + 2k$$ where $|\{n_{e^1}\}|$ is the number of nodes of the graph with degree 1, and $k = e - n + 1$.

That's a worst case scenario where there exists $k$ edges in the graph connecting nodes with degree 2 each, whose removal doesn't create new connected componentes, because removing them will give 2ドルk$ nodes with degree 1 each, and thus $+ 2k$ leaves. If $k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.

Answer 1

Just to make it clear, the problem of finding a spanning tree with a maximum number of leaves is NP-hard. There's a simple 2-approximation algorithm due to Solis-Oba [1] which looks implementable with reasonable effort. In fact, I don't think anything better is known. There are other algorithmic approaches as well (e.g., FPT algorithms), but I'm not sure if these are that practical.

For a good overview of spanning trees in general, you can have a look at the survey of Ozeki and Yamashita [2]. Particularly, Section 6.1 is on spanning trees with many leaves and gives some combinatorial results.

---

[1] Solis-Oba, Roberto. "2-approximation algorithm for finding a spanning tree with maximum number of leaves." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 1998.

[2] Ozeki, Kenta, and Tomoki Yamashita. "Spanning trees: A survey." Graphs and Combinatorics 27.1 (2011): 1-26.

• ABu: I don't need to know/find the maximum leaves tree itself, just the amount of leaves.
• Juho: @Peregring-lk The 2-approximation runs in linear time and will also give you that. Moreover, the survey gives combinatorial results such as the one due to Ding, Johnson and Seymour: if $m \geq n+1/2t(t-1)$ and $n \neq t+2,ドル then there is a spanning tree with more than $t$ leaves, and this is best possible.
• ABu: Thanks, I'm reading it. A question, when it says "with minimum degree k", what does it means? an average degree of at least k, or no node in the graph with less than k neighbours?
• Juho: @Peregring-lk It means that every vertex has degree at least $k,ドル so the latter.