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 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 at 19:04
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 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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