◀ ▲ ▶Branches / Graph-theory / Proposition: A Necessary Condition for a Graph with Shortest Cycles to Be Planar

It turns out that the previous proposition is only a special case of a more general result, which depends on the length $k$ of the shortest cycle of the planar graph. If there is no restriction at all, the shortest cycle in a disconnected graph is always a triangle ($k=3$). With this value for $k$, we obtain the result of the previous proposition with the next, more general result.

Proposition: A Necessary Condition for a Graph with Shortest Cycles to Be Planar

Let $k\ge 3$ be a positive integer and let $G(V,E)$ be a simple, biconnected, planar graph with $|E|$ edges and $|V|$ vertices and shortest cycle length $k.$ Then $$|E|\le \frac{k}{k-2}(|V|-2).$$

Table of Contents

Proofs: 1

Mentioned in:

Proofs: 1
Solutions: 2

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

Github:

References

Bibliography

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