Determine an upper bound


Problem:

Let k>=3 be an integer , and let G be a plane graph of order n(>=k) and size m.

a) If the length of every cycle is at least k, then determine an upper bound B for m in terms of n and k.

b) Show that the bound B obtained in a) is sharp by determining for arbitrary k>=3, a plane graph G of order n and size B, every cycle of which has length at least k.

Solution Preview :

Prepared by a verified Expert
Finance Basics: Determine an upper bound
Reference No:- TGS02060595

Now Priced at $20 (50% Discount)

Recommended (93%)

Rated (4.5/5)