Graphe ayant un 3-cycle
Question.
Un graphe $G$ a $s$ sommets et $a$ arêtes.
Pour quel $k(s)$ est-ce-que
$$
a\geq k(s) \Rightarrow G\; \text{a un cycle d'ordre 3 ?}
$$
Un graphe $G$ a $s$ sommets et $a$ arêtes.
Pour quel $k(s)$ est-ce-que
$$
a\geq k(s) \Rightarrow G\; \text{a un cycle d'ordre 3 ?}
$$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Plus généralement, $k(s) = \left\lfloor\frac{s^2}{4}\right\rfloor +1$, c'est le théorème de Mantel.