Timeline for Maximum number of edges in a planar graph
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 24, 2015 at 17:51 | review | Close votes | |||
| Sep 25, 2015 at 10:26 | |||||
| Sep 24, 2015 at 16:56 | answer | added | Herman Jaramillo | timeline score: 3 | |
| Mar 10, 2013 at 2:25 | comment | added | user9072 | Please don't worry! We have many questions here that are a lot worse. This one is quite alright in my opinion, just slightly too standard. | |
| Mar 10, 2013 at 2:15 | vote | accept | Gorka | ||
| Mar 10, 2013 at 2:05 | comment | added | Gorka | I can delete this whole thing if you want to or not. I'm just happy I gut my answer and a comment from Noam Elkies who I allready knew about because he is well know in the math olympiad world. I can't see the close votes but if you want I'll gladly delete this. | |
| Mar 10, 2013 at 2:01 | comment | added | user9072 | Since there is now also an answer in the techncial sense, we can also leave it open from my point of view (I already voted, but have no strong feelings regarding this). | |
| Mar 10, 2013 at 1:57 | comment | added | user9072 | No problem. Yes for n >= 3, it is 3(n-2); see in particular the subsections "maximal planar graphs" and "Eulers's formula" of the above mentioned page. | |
| Mar 10, 2013 at 1:56 | history | undeleted | Gorka | ||
| Mar 10, 2013 at 1:55 | history | deleted | Gorka | ||
| Mar 10, 2013 at 1:50 | comment | added | Gorka | Oh, ok sorry guys. But just to clarify I never found it on wikipedia. SO then the answer is 3(n-2)??? | |
| Mar 10, 2013 at 1:38 | comment | added | user9072 | Yes it is well known, for example it is on the Wikipedia page Planar graph; voted to close. | |
| Mar 10, 2013 at 1:36 | answer | added | yberman | timeline score: 11 | |
| Mar 10, 2013 at 1:33 | comment | added | Noam D. Elkies | This must be well-known: The maximum is $3(n-2)$ for every $n>2$ (the maxima of $0,0,1$ for $n=0,1,2$ are clear). The upper bound follows from Euler's relation $V-E+F=2$ upon setting $V=n$ and using the inequality $E \geq \frac32 F$. This inequality is sharp iff every face is a triangle. So to $E=3n-6$ can be attained inductively: start from a triangle for $n=3$, and then to get from $n$ to $n+1$ put a new vertex in some triangle and connect it to the triangle's three vertices to split the original triangle into three. | |
| Mar 10, 2013 at 1:06 | history | asked | Gorka | CC BY-SA 3.0 |