Show that a Star graph is balanced

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.