Show any graph G contains an r-partite subgraph H with e(H) ≥ r − 1...

desertiev5

desertiev5

Answered

2022-07-01

Show any graph G contains an r-partite subgraph H with e(H) r 1 r e ( G )
I'm trying to show that for any r 2 any graph G contains an r-partite subgraph H with e(H) r 1 r e ( G )

Answer & Explanation

vrtuljakwb

vrtuljakwb

Expert

2022-07-02Added 13 answers

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 ( v ) r 1 r d G ( v ) , v V ( G ) .
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 1 r d G ( v ) neighbors in it's partition, otherwise there is a set in which v has not more than 1 r d G ( v ) neighbors, so we can put v in that set and increase number of edges. Now we have e ( H ) = 1 2 d H ( v ) 1 2 r 1 r d G ( v ) = r 1 r e ( G ) .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?