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?
 A: 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.)
A: 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.
$$
A: 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.
