# Average branching factor of an undirected graph

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 $$2k$$ 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.

• @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. – Juho Aug 25 '19 at 12:17
• @Peregring-lk It means that every vertex has degree at least $k$, so the latter. – Juho Aug 25 '19 at 13:59