desertiev5

2022-07-01

Show any graph G contains an r-partite subgraph H with e(H) $\ge \frac{r-1}{r}e\left(G\right)$
I'm trying to show that for any $r\ge 2$ any graph G contains an r-partite subgraph H with e(H)$\ge \frac{r-1}{r}e\left(G\right)$

vrtuljakwb

Expert

Actually there is more elementary method then you are thinking about. First of all let's prove that there is r-partite subgraph H such that.
${d}_{H}\left(v\right)\ge \frac{r-1}{r}{d}_{G}\left(v\right),v\in V\left(G\right).$
Let's partition our vertices into r subsets such that the induced bipartite graph has maximum number of edges. Let's take some vertex v. Now we claim that it has not more than $\frac{1}{r}{d}_{G}\left(v\right)$ neighbors in it's partition, otherwise there is a set in which $v$ has not more than $\frac{1}{r}{d}_{G}\left(v\right)$ neighbors, so we can put $v$ in that set and increase number of edges. Now we have $e\left(H\right)=\frac{1}{2}\sum {d}_{H}\left(v\right)\ge \frac{1}{2}\frac{r-1}{r}\sum {d}_{G}\left(v\right)=\frac{r-1}{r}e\left(G\right).$

Do you have a similar question?