The chromatic number of a graph and min degrees of its subgraphs | graph theory | intermediate level

Episode 86.

The chromatic number of a graph and min degrees of its subgraphs | graph theory | intermediate level.
The connection between the chromatic number of a graph and the minimum degrees of its subgraphs | graph theory | intermediate level.

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

Theorem. Any graph $G$ contains a subgraph $H$ with $\Chi(H)=\Chi(G)$ and $\delta(H) \geq \Chi(G) - 1$.
Theorem. For any graph $G$, there is an upper bound on the chromatic number of $G$ in terms of the minimum degrees of its subgraphs: $\Chi(G) \leq \max_{H \subseteq G}{(\delta(H))} + 1$.

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

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

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