A simple graph is triangle-free when it has no simple cycle


A simple graph is triangle-free when it has no simple cycle of length three.

(a) Prove for any connected triangle-free planar graph with v>2 vertices and e edges. e < 2v - 4.

Hint: Similar to the proof that e < 3v - 6.

(b) Show that any connected triangle-free planar graph has at least one vertex of degree three orless.

(c) Prove by induction on the number of vertices that any connected triangle-free planar graph is 4-colorable. 

Hint: use part b

Solution Preview :

Prepared by a verified Expert
Mechanical Engineering: A simple graph is triangle-free when it has no simple cycle
Reference No:- TGS01559760

Now Priced at $10 (50% Discount)

Recommended (98%)

Rated (4.3/5)