SChang
Reputation
Top tag
Next privilege 250 Rep.
 Dec 13 asked How do you find a subset D of set A such that |D| > |N(D)| in a bipartite graph with bipartition A, B (or prove that no such set exist)? Dec 12 accepted Proof related to breadth first search Dec 12 revised Proof related to breadth first search deleted 2 characters in body Dec 12 asked Proof related to breadth first search Dec 12 awarded Scholar Dec 12 accepted Hint on proving this inequality for a planar graph? Dec 12 comment Hint on proving this inequality for a planar graph? Ah, I got it! $t + 6(p-t) \le 2q$ Thank you! Dec 11 awarded Editor Dec 11 revised Hint on proving this inequality for a planar graph? added 78 characters in body Dec 11 comment Hint on proving this inequality for a planar graph? Sorry - (i) is an identity for connected planar graph with p >=3 vertices and q edges. (ii) Euler's formula: Let G be a connected graph with p vertices and q edges. If G has a planar embedding with f faces, then p - q + f = 2. (f = 1 in this case with only 1 outer face for a tree). Dec 11 awarded Student Dec 11 asked Hint on proving this inequality for a planar graph?