# Show that a Star graph is balanced

A star graph $$S_{k}$$ is the complete bipartite graph $$K_{1,k}$$. One bipartition contains 1 vertex and the other bipartition contains $$k$$ vertices. Wikipedia Article

A graph G is balanced if the average degree of every subgraph H is less than or equal to the average degree of G. In other words $$\bar{d}(H) \leq \bar{d}(G)$$.

Show that a star graph is balanced.

I have been able to prove this, however in an extremely ugly and long way using many different cases. I was wondering if there is any easy way to prove this. Any ideas?

• That's a use of "balanced" that is at odds with the usual use in the context of bipartite graphs. Does this property have another name? Jan 11, 2021 at 18:52
• @Joffan It is the standard name for this property for general graphs. The intuition for the name is that the density of the graph is "spread out" in a balanced way, as opposed to being concentrated in a denser core. For bipartite graphs, there's another notion of balance, so we get a conflict of intuition and terminology there... Jan 11, 2021 at 19:04

All trees are balanced, so in particular stars are balanced.

An $$n$$-vertex tree has average degree $$2-\frac 2n$$. Any subgraph of average degree $$2$$ can be reduced to a subgraph of minimum degree $$2$$ by removing leaves, but a subgraph of minimum degree $$2$$ would contain a cycle. Trees don't have cycles, so any subgraph of a tree has average degree less than $$2$$. However, for a $$k$$-vertex subgraph, the largest possible average degree less than $$2$$ is $$2 - \frac 2k \le 2 - \frac 2n$$.

(In fact, all trees are strictly balanced, since the only way to get $$2 - \frac2k = 2 - \frac2n$$ is to have $$k=n$$, taking the entire tree as a subgraph.)

By direct computation,

$$\widetilde{d}(S_k) = \frac{k + \overbrace{1 + \cdots + 1}^{k}}{k+1} = 2k/(k+1).$$

Let's enumerate the vertices of $$S_k$$ as $$v_0, \ldots, v_k$$ with $$d(v_0) = k$$ and $$d(v_i) = 1$$ otherwise.

Pick a subgraph $$H \leq S_k$$. Suppose that there are $$v,w \in H$$ which are not connected in $$H$$ but they in fact are connected in $$S_k$$. Then adding such an edge to $$H$$ can only increase its average degree. Thus, for our objective, this means that we can wlog assume our subgraph $$H$$ is full.

There are only two possibilities: either $$H$$ contains $$v_0$$, and is isomorphic to $$S_j$$ for $$j \leq k$$, or $$H$$ has average degree zero.

Hence, we are left with showing that $$2j/(j+1)$$ is an increasing sequence: indeed,

$$2j/(j+1) \leq 2k/(k+1) \iff 2jk+2j \leq 2kj+2k \iff j \leq k.$$

• Right, thanks :) Fixed Jan 11, 2021 at 18:56

It is clear that $$\bar{d}(S_k) = \frac{k+k\cdot1}{k+1} = \frac{2k}{k+1} = 2-\frac{2}{k+1}$$

Now, in $$H$$, we can consider only two cases:

Case 1: Center vertex $$v \notin H$$ (vertex with degree $$k$$ in star graph). Then, $$H$$ has no edges so $$\bar{d}(H) = 0$$,

Case 2: Center vertex $$v \in H$$. If $$H$$ has all the vertices but missing some of the edges, then clearly $$\bar{d}(H) < \bar{d}(S_k)$$ since we are decreasing the total degree while keeping the number of vertices same. So, suppose $$H$$ has $$n$$ vertices of degree $$1$$ with $$n \le k$$ (here, note that $$H$$ still may be missing some edges but it is enough to check the maximal case, in which we have a star graph $$S_n$$). Then, we have $$\bar{d}(H) = \frac{2n}{n+1} = 2 - \frac{2}{n+1}$$

So, all that's left is to compare $$2-\dfrac{2}{k+1}$$ and $$2-\dfrac{2}{n+1}$$ where $$n \le k$$. But, it is easy to see that

$$2-\dfrac{2}{k+1} \ge 2-\dfrac{2}{n+1}$$

So, we are done.