Prove that every graph has a bipartition \(V ( G ) = X \cup Y\) with the property that \(e ( X , Y ) \geq e ( G ) / 2\) . Further, show that if G is cubic then we can achieve \(e ( X , Y ) \geq\) \(n ( G ) = 2 e ( G ) / 3\)
Large cuts in graphs and cubic graphs
P-UNLJ04-08
- Area
- Topology
- Seen at
- UNL
- Years
- 2004
- Status
- draft