Awesome q2a theme
0 votes
30 views
ago in Graph Theory by (9 points) | 30 views

1 Answer

+1 vote
Best answer

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$$

ago by (2.9k points)
selected ago by
+1
32674 if the vertices are numbered otherwise we need to remove isomorphic graphs.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,968 questions
3,119 answers
14,340 comments
95,792 users