Bipartite Simple Graph

**sanorita_belle** · May 2nd 2009, 07:49 PM

Can anyone please help me with this question? How can i start it?

Show that if G is a bipartite simple graph with v vertices and e edges, then e ≤ v²/4

**NonCommAlg** · May 3rd 2009, 12:23 AM

Originally Posted by sanorita_belle

Can anyone please help me with this question? How can i start it?

Show that if G is a bipartite simple graph with v vertices and e edges, then e ≤ v²/4

let $V$ be the set of vertices. then $V=A \cup B,$ where $A \cap B= \emptyset, \ |A|=m, \ |B|=n.$ clearly $v=m+n$ and $e \leq mn.$ we also have $mn \leq \frac{(m+n)^2}{4}$ because $(m-n)^2 \geq 0.$

**sanorita_belle** · May 3rd 2009, 12:37 PM

Thanks alot

Thread: Bipartite Simple Graph

LinkBack

Thread Tools

Display

Bipartite Simple Graph

Similar Math Help Forum Discussions

Graph theory, bipartite Graph

complete bipartite subgraph of a graph

Bipartite graph proof

Bipartite Graph

Bipartite graph problem

Search Tags