5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Joffan
    Jan 11, 2021 at 18:52
  • 1
    $\begingroup$ @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... $\endgroup$ Jan 11, 2021 at 19:04

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Right, thanks :) Fixed $\endgroup$
    – qualcuno
    Jan 11, 2021 at 18:56
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .