Existence d'un graphe connecté

Bonjour,

Quelle est la quantification sur $n$ ?

Bonjour,

Est ce que c'est $\forall n$ ou $\exists n$ ?

Cordialement,

Rescassol

Pour $\deg(u)+\deg(v)=n-1,n-2,n-3,\ldots$ on fait la même chose avec respectivement $n=3,4,5,\ldots$ sommets.

La racine de l'arbre $x_1$ est de degré $n-1$ et les autres sommets sont des feuilles de degré $1$.

Seules les paires de feuilles sont non adjacentes dans ce graphe.

Bien sûr, on a aussi des solutions triviales où le $\forall u,v$ n'a pas d'instances comme par exemple dans le graphe vide ou un triangle etc....bref, n'importe quel graphe complet $K_n$.

En généralisant le graphe de serge burckel ci-dessus on trouve une solution pour tout $n$ pair.

En effet si $n$ est pair, on choisit les $\dfrac{n-2}{2}$ premiers entiers et on les relie tous entre-eux. On obtient un graphe $G$ complet. Ensuite on relie chacun des $\dfrac{n}{2}+1$ entiers restants à tous les sommets de $G$.

Je viens à peine de me rendre compte que si on suppose que dans l'énoncé d'evariste21 le quantificateur sur le $n$ est $\forall$ alors le graphe complet à $n$ sommets est une solution B-)-

Je laisse finir le calcul pour $n=8$ et vous les donne......oui c'est bien ça....aux virgules près :


1, "(16)(17)(18)(26)(27)(28)(36)(37)(38)(46)(47)(48)(56)(57)(58)(67)(68)(78)"
2, "(16)(17)(18)(26)(27)(28)(34)(35)(38)(45)(48)(58)(68)(78)"
3, "(16)(17)(18)(26)(27)(28)(34)(35)(38)(45)(47)(56)"
4, "(16)(17)(18)(25)(27)(28)(35)(36)(38)(45)(46)(47)"
5, "(16)(17)(18)(25)(27)(28)(34)(37)(38)(47)(48)(57)(58)(67)(68)(78)"
6, "(16)(17)(18)(25)(27)(28)(34)(36)(38)(45)(48)(58)(68)(78)"
7, "(16)(17)(18)(25)(27)(28)(34)(36)(38)(45)(47)(56)"
8, "(16)(17)(18)(25)(27)(28)(34)(36)(38)(45)(46)(57)"
9, "(16)(17)(18)(25)(27)(28)(34)(35)(36)(45)(46)(78)"

Si $n$ est impair alors il n'y a que la solution triviale $K_n$.

On va voir si le gribouillis que j'ai fait sur ma feuille tient la route...

Soit $n$ impair. On remarque que si $x,y$ sont deux sommets de degrés impairs (respectivement pair) alors il sont forcément reliés. Notons alors $I$ et $P$ les ensembles des sommets de degrés impair et pair respectivement. $I$ et $P$ sont deux sous-graphes complets par la remarque précédente.

Supposons $I$ et $P$ non vides, par connexité il existe $u\in I$ et $v\in P$ reliés.

On sait que $|I|$ est pair (découle du fait que la somme des degrés d'un graphe est égale au double du nombre d'arêtes) et donc $|P|$ est impair.

Le sommet $u$ est relié à tous les autres sommets de $I$ qui sont au nombre de $|I|-1$ et à $v$. On en déduit qu'il est relié à un nombre pair de sommets de $P$ (car $\deg(u)$ est impair).

Donc $\deg(u)=|I|-1+2\ell_u$ avec $\ell_u>0$.

Le sommet $u$ ne peut pas être relié à tous les sommets de $P$ car autrement son degré serait égal à $n-1$ qui est pair. Soit donc $w\in P$ tel que $u$ et $w$ ne sont pas reliés.

$w$ est relié à tous les autres sommets de $P$ et à un nombre pair (éventuellement nul) de sommets de $I$. Donc $\deg(w)=|P|-1+2\ell_w$ avec $\ell_w\geq 0$.

Pour finir on a $n-2=\deg(u)+\deg(w)=|I|-1+2\ell_u+|P|-1+2\ell_w=n-2+2(\ell_u+\ell_w)$. Donc $\ell_u+\ell_w=0$ ce qui est impossible car $\ell_u>0$.

Donc $I$ ou $P$ est vide et le graphe est complet (et c'est forcément $I$ qui est vide).

PS : serge burckel, 56 solutions pour $n=10$, OK. Elles sont non-isomorphes deux à deux ?

Dans les exemples que tu as trouvés, serge, les ensembles des degrés des sommets des graphes trouvés ont-ils des particularités ? y a-t-il des cas "atypiques" ?