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 )

Question

Show any graph G contains an r-partite subgraph H with e(H)   ≥            r      −      1        r    e  (  G  )I&#039;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  )

vrtuljakwb · Accepted Answer

Actually there is more elementary method then you are thinking about. First of all let&#039;s prove that there is r-partite subgraph H such that.       d    H    (  v  )  ≥            r      −      1        r        d    G    (  v  )  ,  v  ∈  V  (  G  )  .Let&#039;s partition our vertices into r subsets such that the induced bipartite graph has maximum number of edges. Let&#039;s take some vertex v. Now we claim that it has not more than       1    r        d    G    (  v  ) neighbors in it&#039;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  )  .

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

Answered question

Answer & Explanation

New Questions in Precalculus