Existence d'un graphe connecté
Bonjour
Montrer qu'il existe un graphe connecté tel que $\deg(u)+\deg(v)=n-2$ pour chaque paire de sommets non adjacents $u,v$ dans le graphe et $n$ le nombre de sommets.
Merci.
Montrer qu'il existe un graphe connecté tel que $\deg(u)+\deg(v)=n-2$ pour chaque paire de sommets non adjacents $u,v$ dans le graphe et $n$ le nombre de sommets.
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Quelle est la quantification sur $n$ ?
Est ce que c'est $\forall n$ ou $\exists n$ ?
Cordialement,
Rescassol
graphe connecté : $(x_1,x_2),(x_1,x_3),(x_1,x_4)$
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.
Trouver ou décrire toutes les solutions semble difficile....mais en trouver une était assez facile.
{1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}
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 vois par programme qu'il y a toute une tribus de solutions non triviales à $8$ sommets. Au moins $9$ graphes non isomorphes.
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)"
en tout cas, jusqu'à $n=10$ c'est vrai et pour $10$ déjà $56$ solutions non triviales (le sommet $10$ est noté $0$) :
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 ?
En fait $63$ pour l'instant.....OUI non isomorphes deux à deux.
En fait si je ne me trompe pas on a le résultat suivant :
Un graphe $G$ non complet à un nombre $n$ pair de sommets vérifie la condition du premier message http://www.les-mathematiques.net/phorum/read.php?34,2316002,2316002#msg-2316002 ssi il existe un entier $r\in [\![0,\frac{n-2}{2}]\!]$ et un graphe régulier $R$ de degré $\frac{n-2}{2}-r$ à $n-r$ sommets tel que $G$ est isomorphe à $K_r \bowtie R$.
Ici $K_r$ est le graphe complet à $r$ sommets et $\bowtie$ désigne l'opération qui consiste à relier chaque sommet du premier graphe à chaque sommet du second.
Par conséquent, étudier les différentes classes d'isomorphismes de ce type de graphe revient à étudier les graphes réguliers...
Par exemple on constate en prenant $r=0$ ci-dessus que l'on tombe sur le cas où $G$ est isomorphe à un graphe régulier de degré $\dfrac{n-2}{2}$. Si $r=\dfrac{n-2}{2}$ on tombe sur le cas décrit ici http://www.les-mathematiques.net/phorum/read.php?34,2316002,2316502#msg-2316502.