Branches History Index

◀ ▲ ▶Branches / Graph-theory / Proposition: A Necessary Condition for a Graph to be Planar

Proposition: A Necessary Condition for a Graph to be Planar

Let $G(V,E)$ be a simple, biconnected, and planar graph. Then the number of its edges is less than three times the number of its vertices less $6$, formally $$|E|\le 3|V|-6.$$

Table of Contents

Proofs: 1

Mentioned in:

Propositions: 1
Solutions: 2

Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs

References

Bibliography

  1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000