graphe et distance euclidienne

[invitef7cb9c5c]

Bonsoir,
la dernière question d'un exercice reste totalement obscure
en particulier pourquoi si on a pas de K_2,3 alors le nombre de paire < n^3/2
voilà l'énoncé
Soit G = (S;A) un graphe simple à n sommets et m arêtes. On suppose de plus qu’il existe un entier naturel s tel que G ne contienne pas K2;s. On considère enfin l’ensemble suivant :
T = {(u; (v;w)) éléments de S * P2(S) : (u; v) élément de A et (u;w) élément de A}
Soit S un ensemble de n points du plan R2, muni de la distance
euclidienne d.
Montrer que, pour n assez grand, le nombre de paires (a; b)élément de P2(S)
telles que d(a; b) = 1 est inférieur à n^3/2 ?
Indication : On définira le graphe G = (S;A) dont les sommets sont les éléments de
S et dont les arêtes sont précisément les paires fa; bg 2 P2(S) telles que d(a; b) = 1.
Le graphe G peut-il contenir K2;3 ?
merci pour votre aide
fifrelette
-----

[inviteafa56da9]

Donner le sujet sous cette forme dans l'autre fil de discussion aurait été au moins aussi efficace que de créer un nouveau sujet...

L'énoncé contient beaucoup d'informations inutiles, on commence par faire le tri :

Soit S un ensemble de n points du plan R² muni de la distance euclidienne. Soit G=(S,A) le graphe tel que (u,v) est dans A si d(u,v)=1.
1. Montrer que G ne contient pas K₂,₃.
2. En déduire que |A|<n^{3/2} pour n assez grand.

Pour la question 1, apparemment tu as su répondre, mais à tout hasard : supposons qu'un sommet x est relié à 3 sommets u,v et w. Alors ils se trouvent sur le cercle de centre x et de rayon 1. Maintenant, il est assez facile de voir que le seul point du plan situé à distance 1 de u, v et w est x.

Pour la question 2, j'ai tendance à penser qu'il y a dû avoir des questions préliminaires qui peuvent t'aider à répondre. Je pense cela car la première partie de l'énoncé que tu donnes (sur K₂,s et la définition de l'ensemble T) n'apparaissent pas dans cette question. Du coup, peut-être que les questions intermédiaires peuvent t'aider à répondre ? Là très honnêtement, en y réfléchissant (un peu rapidement), je ne vois pas comment faire (à part que vu que ton graphe ne contient pas K₂,₃, un sommet ne peut être relié à plus de trois sommets que si ceux si ne sont pas reliés entre eux. Donc ça limite clairement le nombre possible d'arêtes. Ensuite, il faudrait regarder un peu plus précisément cette idée je pense pour trouver la borne annoncée.)

[invitef7cb9c5c]

bonsoir BGT
en effet j'aurai pu reprendre le fil de discussion déjà existant, je pensais que c'était plus clair avec un nouveau, dorénavant je saurai qu'il est préférable de rester dans le même fil
merci pour les explications à propos de l'absence de K_2,3
pour finir, il est vrai que je n'ai pas donner tout l'énoncé et que précédemment on a trouvé une inégalité où si je remplace une des variable par 3 du K_2,3 et pour n assez grand j'obtiens le résultat attendu
merci pour votre aide
fifrelette