Talk:List of graphs by edges and vertices

Sparcity of planar graphs

Since understanding some maths is nothing but writing from scratch the required proofs, we have:

1. Planar means that (segments of) straight lines are used to draw the edges, and surely not topological horrors.
2. Take the complementary of the edges w.r.t. the whole plane. And then take the connected components. This gives the so-called faces.
   Suppose the graph is finite and compute $Euler=V+F-E$. Suppose the graph is simple and connected and that $F>1$.
   At least, there is an inner face that shares an edge with the outer face. Suppress this edge. The remaining graph is simple and connected again, while $Euler$ remains unchanged. Dosim, repetare.
   This leaves a connected graph without cycles, i.e. a tree.
   Suppose that each vertex has two neighbors, build an infinite path and conclude to a cycle.
   Suppose that $V>2$, and suppress a vertex with only one neighbor, and the corresponding edge also. The remaining graph is simple and connected again, while $Euler$ remains unchanged. Dosim, repetare.
   At the end, we have $F=E=1,V=2$.
   Therefore, $V+F-E=2$ (the Euler formula).
3. Define the augmented graph as obtained by repeating the edges that are adjacent to only one face.
   Define the boundary length of a given face as the number of its adjacent (augmented) edges. This name is coined from the fact that these edges, correctly ordered, describe the topological boundary of the given face (remember: a face is an open subset of the plane)
   Let $B$ be the sum of the boundary lengths of the faces (the outer face included). Then obviously $B=2E$
   Moreover, suppose $V>2$. Then even the outer face is adjacent to at least 3 augmented edges, so that $3F\leq B$, proving that $3(2+E-V)=_{Euler}3F\leq 2E$.
   This is the required necessary condition $E\leq 3V-6$

And therefore, only the Descartes snarks are N/A. Pldx1 (talk) 17:17, 28 December 2018 (UTC)

@Pldx1: Yup, that's a classic criterion for checking planarity ("Theorem 1" in Planar graph#Other planarity criteria). Thanks for noticing that it can be applied in the list! (By the way, the fact that planar graphs can be drawn with straight lines is known as Fáry's theorem, though your proof works basically without change with either definition.) Tokenzero (talk) 11:56, 31 December 2018 (UTC)

@Tokenzero:. Yes, you're right, this is a classical criterion. After a cursory reading of the corresponding pages, I have not found a convincing sketch of the proof. Since this is the only method to be sure of what are the required hypotheses, I have written my own tentative sketch. No intent to provide anything original ! Pldx1 (talk) 18:18, 5 January 2019 (UTC)