Bipartite subgraph

Task number: 3604

Show that every graph with \(m\) edges has a bipartite subgraph with at least \(\frac{m}2\) edges.

  • Hint

    Imagine that you are building the graph by adding one vertex at a time.

  • Solution

    We proceed by induction on the number of vertices (the assertion holds for a one-vertex graph).

    Choose an arbitrary vertex \(u\). Consider \(G'=G\setminus u\); by the inductive hypothesis \(G'\) has a bipartite subgraph with at least \(\frac{|E_{G'}|}2\) edges. Let \(A\) and \(B\) be the parts (partitions) of this bipartite graph.

    We will expand one of these parts by adding \(u\) in such a way that we may add at least \(\frac{\deg_G(u)}2\) edges to the bipartite graph – which is certainly possible if we add \(u\) to the part in which it has fewer neighbors.

    The resulting bipartite subgraph has at least \(\frac{|E_{G'}|}2+\frac{\deg_G(u)}2=\frac{|E_{G}|}2\) edges.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email