1.

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»

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).


Discussion

No Comment Found

Related InterviewSolutions