Graphe ayant un 3-cycle

soland · December 2017

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 ?}
$$

GaBuZoMeu · December 2017

Graphe simple, je suppose ?

soland · December 2017

Oui, et non orienté.

GaBuZoMeu · December 2017

$k(2)=3$.

Math Coss · December 2017

$k(3)=3$ et $k(4)=5$ (pour un nombre maximal d'arêtes égal à $6$).

Le Lui ou un Autre · December 2017

Pour $s$ pair, le graphe possédant le plus d'arêtes sans cycle d'ordre 3 est le graphe biparti $K_{s/2,s/2}$ qui possède donc $\frac{s^2}{4}$ arêtes.

Plus généralement, $k(s) = \left\lfloor\frac{s^2}{4}\right\rfloor +1$, c'est le théorème de Mantel.

soland · December 2017

Merci pour ces informations.

Graphe ayant un 3-cycle

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 32