Large Bipartite Subgraph

Name: Large Bipartite Subgraph
Uploaded: 2024-11-06T17:36:26Z
Duration: 6 min 44 s
Description: A simple application of the probabilistic method in combinatorics: a proof that every graph contains a large bipartite subgraph with at least half of the edges.

6:44

Up Next

Lower Bounds to Ramsey Numbers

Continue

A simple application of the probabilistic method in combinatorics: a proof that every graph contains a large bipartite subgraph with at least half of the edges.