Awesome q2a theme

+1 vote

Best answer

If a

maximal planar graphhas vverticeswith v > 2, then it has precisely 3v − 6edgesand 2v − 4 faces

A graph with greater than 3v-6 = 3*6-6 = 12 will never be planar. All graph with 6 vertices and less than equal to 12 edges will be planar.

A complete graph with 6 vertices has $6\choose 2$$=15$ edges, we have to choose at most 12 edges from these 15, i.e, $${15\choose0} + {15\choose1} + {15\choose2} + … + {15\choose12}$$

$$=2^{15} – {15\choose13} – {15\choose14} – {15\choose15}$$

$$= 32768 - 105 - 15 - 1$$

$$= 32674$$

8,968 questions

3,119 answers

14,340 comments

95,792 users