statement theorem
Euler's formula for planar graphs
Statement
Let be a finite connected planar graph, drawn in the plane with no crossing edges. Let , and be the numbers of vertices, edges and faces of the drawing, where the unbounded face counts. Then .
Remarks
Proof idea: if the graph has a cycle, delete an edge of the cycle. This removes one edge and one face. At the end you have a spanning tree, with and . The same formula holds for the vertices, edges and faces of a convex polyhedron.
Explanations
L1 human
Draw a connected graph without crossings and count its vertices, edges and regions. Vertices minus edges plus regions is always . For a square, this is .
What this node needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
The writing levels say how complete the text of a node is. They do not measure its truth.
What this needs
To read this node, read these 6 nodes in this order. The foundations come first, and the list ends with this node.
- no evidence level
- Graph definition
- Planar graph definition
- Walk definition
- Reachability definition
- Connected graph definition
- Euler's formula for planar graphs statement
What depends on this
3 nodes use this node, directly or through other nodes.
- K5 and K3,3 are not planar 030A3FHN14
- Kuratowski's theorem 0J6G5NJC5R
- Edge bound for planar graphs 0SM1REAVYJ
Sources
- Web https://en.wikipedia.org/wiki/Euler_characteristic, Plane graphs
What links here
Used by
- Edge bound for planar graphs 0SM1REAVYJ