Let G be a simple triangle free graph. Prove that the min size of an egde cover (B'(G)) is greater than or equal to the min degree of G (delta(G)).

I don't have any idea on how to prove this. Can someone show the proof? Thanks a lot!

Printable View

- Mar 27th 2012, 10:08 PMjzelltGraph theory
Let G be a simple triangle free graph. Prove that the min size of an egde cover (B'(G)) is greater than or equal to the min degree of G (delta(G)).

I don't have any idea on how to prove this. Can someone show the proof? Thanks a lot!