Question

Suppose G be a connected planar graph of order n≥5 and size m. If the length of the smallest cycle in G is 5, then which of the following is true?

(a) (m+n)^4>=mn

(b) m≤5/3(n−2)

(c) (m^2+n)/3

(d) n>=(6/5)(n+1)

The question was posed to me in my homework.

This question is from Planarity, Degree and Coloring of Graph in section Graphs of Discrete Mathematics

Answer 1

Correct choice is (b) m≤5/3(n−2)

The best explanation: Because G is connected and planar, Euler’s theorem is bound to be involved. Let f denote the number of faces so that n−m+f=2. Because the length of the smallest cycle in G is 5, every face has at least 5 edges adjacent to it. This means 2m≥5f because every edge is adjacent to two faces. Plugging this in yields 2=n−m+f≤n−m+2/5m=n−3/5m, and hence m≤5/3(n−2).