Lemma regarding Balanced Graph

95 Views Asked by At

I am trying to prove a lemma which states that if Let $G= G_1 \sqcup . . . \sqcup G_k$ be a disjoint union of $k$ connected graphs. Prove that $G$ is balanced if and only if $ρ(G_1) = . . . = ρ(G_k)$ and all $ G_1. . . G_k$ are balanced.
Here $ρ(G_1) = . . . = ρ(G_k)$ stands for density of the respective graph.

What I have tried: Since G is a disjoint union of $k$ connected graphs then the density of G can be given as $ρ(G)= \frac{e_{G_1} +...e_{G_k}}{v_{G_1} +...v_{G_k}}$. Here $e_{G_1}. ...e_{G_k}$ imply the no of edges of the respective graph and $v_{G_1}...v_{G_k}$ imply the no of vertices of respective graph.$ρ(G)= \frac{e_{G_1} +...e_{G_k}}{v_{G_1} +...v_{G_k}}$ will be either less than or equal to max {$\frac{e_{G_1}}{v_{G_1}},...\frac{e_{G_k}}{v_{G_k}}$} which is basically equals to max {$ρ(G_1),. . .,ρ(G_k)$}. Now I am stucked over here. Could you please help me further.

Thank you in advance.

1

There are 1 best solutions below

0
On

You are almost there. You have $$ \frac{e(G_1) + \dots + e(G_k)}{v(G_1) + \dots + v(G_k)} \le \max\left\{\frac{e(G_1)}{v(G_1)}, \dots, \frac{e(G_k)}{v(G_k)}\right\} $$ or equivalently $\rho(G) \le \max\{\rho(G_1), \dots, \rho(G_k)\}$. The extra bit you need to know is that equality holds only if $\rho(G_1) = \dots = \rho(G_k)$.

This happens because the expression $\frac{e(G_1) + \dots + e(G_k)}{v(G_1) + \dots + v(G_k)}$ is a kind of average of $\frac{e(G_1)}{v(G_1)}, \dots, \frac{e(G_k)}{v(G_k)}$. In fact, it's a weighted arithmetic mean, with the weights just being the number of vertices. The average can only be equal to the maximum if all of the terms you're averaging are equal.

Once you have that, you can conclude that unless $\rho(G_1) = \dots = \rho(G_k)$, there will be some $G_i$ with $\rho(G_i) > \rho(G)$, which tells you that $\rho(G)$ is not balanced.

You should also be able to show that if $G_i$ is not balanced for some $i$, then the subgraph of $G_i$ that demonstrates this also has higher density than $G$, in which case $G$ is not balanced either.


It remains to show the other direction: that if $\rho(G_1) = \dots = \rho(G_k)$ and each $G_i$ is balanced, then $G$ is balanced.

In general, if $H$ is a subgraph of $G$, then $H$ can be written as a disjoint union $H_1 \sqcup H_2 \sqcup \dots \sqcup H_k$, where each $H_i$ is a subgraph of $G_i$. We have $$ \frac{e(H_1) + \dots + e(H_k)}{v(H_1) + \dots + v(H_k)} \le \max\left\{\frac{e(H_1)}{v(H_1)}, \dots, \frac{e(H_k)}{v(H_k)}\right\} $$ so $\rho(H) \le \max\{\rho(H_1), \dots, \rho(H_k)\}$. This plus the assumptions we've made in this case should be all you need to show that $\rho(H) \le \rho(G)$.