I was going through a handout. It had the text (p.4):

Let $G$ be a tree and $v$ be any vertex of $G$. Let $v_1,v_2,v_3,\dots, v_t$ be vertices adjacent to $v$. Let $e_i$ be the edge joining $v$ and $v_i$. Let $T_i$ be subtree containing $v_i$ after removing edge $e_i$. Let $f(v)= \max_{i=1}^t |V(T_i)|$.

Since $\sum |V(T_i)|=n-1$, if $f(v)$ is large, then the tree looks unbalanced. If $f(v) \approx (n-1)/t$ then the tree looks balanced.

however it didn't explain what a balanced graph is. What is a balanced tree?

  • $\begingroup$ Have you tried searching for "balanced tree" with your favorite search engine? $\endgroup$ – John Douma Apr 12 at 12:12
  • 1
    $\begingroup$ @JohnDouma It wouldn't really help, in this case. $\endgroup$ – Misha Lavrov Apr 12 at 12:23

There's a couple notions of a "balanced graph" in general, but the handout isn't referring to any of them. It's somewhat related to the notion of balance used in balancing binary search trees, but that's actually optimizing a different quantity in a different context for a different purpose.

Instead, the word "balancing" is being used for intuition, and the intuition you should have is this. If $v$ is a vertex in an $n$-vertex tree $T$ with $\deg(v)=t$, then deleting $v$ from $T$ leaves a forest $T-v$ with $t$ components. (Each of $v$'s former neighbors is now in a different component of $T-v$.)

If there are $n$ vertices in $T$, there are $n-1$ in $T-v$, so the average order of a component is $\frac{n-1}{t}$. We defined $f(v)$ to be the maximum order of any component. Thus:

  • If $f(v) \approx \frac{n-1}{t}$, then the largest component of $T-v$ is approximately average, which means all components must be approximately average. They are "balanced" in that each one has about the same number of vertices.
  • If $f(v)$ is much larger than $\frac{n-1}{t}$, then the largest component of $T-v$ is much larger than average. The components are unbalanced: one has many more vertices than the others.

Often we split a tree by deleting an edge, and we would like the two resulting components to be as equal as possible. If we delete an edge $vv_i$, then one component of $T-vv_i$ is the component of $T-v$ containing $v_i$, and the other component is everything else. The best thing we can do is delete the edge to the largest component of $T-v$: in that case, one component has $f(v)$ vertices, and the other has $n - f(v)$.

Relatedly, for the "tree balancing exercise" on the next page of the hand out, see this post for why the upper bound on $\min_v f(v)$ isn't very good, and could be significantly improved. (To be fair, all we need is a lower bound on the smaller of $f(v)$ and $n-f(v)$, and $f(v)$ is usually the bottleneck there.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.