Upper bound on chromatic number of graph in terms of number of edges | graph theory | elementary

Episode 72.

Upper bound on chromatic number of graph in terms of number of edges | graph theory | elementary.
The upper bound on the chromatic number of a graph in terms of the number of edges | graph theory | elementary level.

Branch of mathematics: graph theory.
Difficulty level: elementary.

Theorem. For a graph with $m$ edges, we have $\Chi(G) \leq \frac{1}{2}+\sqrt{2m+\frac{1}{4}}$.

Mathematics. Discrete Mathematics. Combinatorics. Graph theory.
#Mathematics #DiscreteMathematics #Combinatorics #GraphTheory

The same video on YouTube:
https://youtu.be/PU9jLwKvE8E

The same video on Telegram:
https://t.me/mathematical_bunker/96