Problem 58389. Minimum number of crossings in a complete graph

  • Created by HH
This problem is related to problem 58384.
A complete graph may be drawn in different ways, such that the number of line crossings differs between drawings.
To date, the question of how to draw the graph so as to minimize the number of crossings remains unsolved.
Nevertheless, an upper bound can be calculated for the number of crossings, based on the number of vertices in the graph.
Given the number of vertices, n, calculate the upper bound, b, for the minimum number of line crossings in the resulting complete graph.
Example:
n = 6;
b = 3
Solve

Solution Stats

100.0% Correct | 0.0% Incorrect
Last Solution submitted on Dec 18, 2025

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers12

Suggested Problems

More from this Author45

Problem Tags

graph theory

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!