10 votes 10 votes Maximum number of edges in a planar graph with $n$ vertices is _____ Graph Theory gate1992 graph-theory graph-planarity easy fill-in-the-blanks + – Kathleen asked Sep 12, 2014 • edited Apr 19, 2021 by Lakshman Bhaiya Kathleen 5.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 13 votes 13 votes Answer: 3n - 6 Ref: http://mathoverflow.net/questions/124116/maximum-number-of-edges-in-a-planar-graph Rajarshi Sarkar answered Apr 25, 2015 • selected Apr 25, 2015 by Arjun Rajarshi Sarkar comment Share Follow See all 4 Comments See all 4 4 Comments reply suneetha commented Nov 14, 2018 reply Follow Share i think it is 2n-2 if n=2 then edges will be 1 it is also a planar graph but according to your equation it becomes 0 0 votes 0 votes Raghav Khajuria commented Nov 14, 2018 reply Follow Share @ suneetha 2n-4 (not 2n-2) its true when the graph has no cycle of lenght 3. 0 votes 0 votes suneetha commented Nov 14, 2018 reply Follow Share they didn't represent about whether it should have cycle or not? 0 votes 0 votes suneetha commented Nov 14, 2018 reply Follow Share if n is even then the equation comes like 2(n-1) if n is odd then the equation comes like 2n-1 then what is the answer for this question? 0 votes 0 votes Please log in or register to add a comment.