◀ ▲ ▶Branches / Graph-theory / Solution

Solution

(related to Problem: Checking if $K_{3,3}$ is Planar)

• Suppose that the complete bipartite graph $K_{3,3}$ is planar is planar.
• Note that the shortest cycle in $K_{3,3}$ is of length $4.$
• A necessary condition for a graph to be planar with shortest cycle requires that $$|E|\le \frac{k}{k-2}(|V|-2),$$ where $|E|$ ist the number of its edges and $|V|$ is the number of its vertices.
• For $K_{3,3}$ this condition means that $$|E|=9\le \frac{4}{2}(6-2)=2\cdot 4=8.$$ which is false.
• Therefore, $K_{3,3}$ is not planar.

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