Question

What is total number of planer graph can be formed with 6 vertices ?

Comments

https://csedoubts.gateoverflow.in/blog/1/guidelines-to-users

Answer 1

If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 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$$

Comments

32674 if the vertices are numbered otherwise we need to remove isomorphic graphs.