Formule sur les graphes

Bonsoir,
Il y a par exemple cet argument:
Notons $A = (a_{i,j})_{1\leq i,j \leq n}$ la matrice d'adjacence du graphe, c'est à dire la matrice $n\times n$ définie par: $a_{i,j} = 1$ si $\{i,j\}$ est une arête du graphe et $a_{i,j}= 0$ sinon.
$I$ est la matrice-unité d'ordre $n$, $E$ est la matrice $n\times n$ dont tous les coefficients sont égaux à $1$, et $X$ désigne le vecteur-colonne dont les $n$ coordonnées sont égales à $1$.
Le fait que le graphe soit $k$-régulier entraine que $AX=kX$.
La seconde information entraine que $A^2 = (k-1)I + E$ . (le coefficient $(i,j)$ de $A^2$ est le nombre de chemins de longueur $2$ menant de $i$ à $j$.)
Ainsi: $k^2X=A^2X=(k-1)X+nX$ et cela entraine: $k^2 =k-1+n$.
Amicalement.

Re,

Soient $\mathcal A$ l'ensemble des arêtes, $\mathcal S$ celui des sommets, $s$ un élément de $\mathcal S\:$ et $\:\mathcal E=\left\{(x,y)\in \mathcal S^2 \mid \{s,x\} \in \mathcal A \:\: \text{et}\:\:\{x,y\} \in \mathcal A\right\}$.
La $k$-régularité du graphe entraine que $\text{Card}\:\mathcal E= k^2$.
En distinguant le cas où $y=s$ de ceux où $y\neq s$, et en utilisant la seconde hypothèse, il vient: $\:\:\text{Card}\:\mathcal E = k +(n-1)$, puis l'égalité cherchée .
Ce double décompte de $\text{Card}\: \mathcal E$ correspond en fait aux deux expressions de $A^2X$ apparaissant dans mon précédent message.
A noter qu'il n'existe, me semble-t-il, qu'un seul graphe ayant la propriété décrite dans le message initial: le graphe complet $\mathcal K_3$, c'est à dire le triangle.

Amicalement,

Bonjour babsgueye,

Je suis désolé, mais je suis au maximum de mes possibilités, et ne vois pas bien le manque de rigueur dans ce nouveau choix de $\mathcal E$, qui a l' avantage de montrer que la conclusion $k^2-k =n-1$ demeure vraie si on affaiblit légèrement les hypothèses en supposant que le graphe est $k-$régulier et qu'il existe seulement un sommet $s$ qui possède avec chacun des autres sommets un unique "voisin" commun.
$\text{Card } \:\mathcal E = k^2$ car, pour fabriquer les couples $(x,y)$ de $\mathcal E$, il y a $k$ choix possibles pour $x$ (voisins de $s$) qui se combinent à $k$ choix possibles pour $y$ (voisins de $x$).
D'autre part, selon moi, le seul graphe obéissant aux hypothèses énoncées dans le message initial correspond au cas où $k=2$ et $n=3$, c'est à dire $\mathcal K_3$ et je pense détenir une preuve correcte qu'il n'en existe pas d'autre. Si tu en connais un avec, par exemple, $k=3$ et $n=7$, n' hésite pas à me le décrire.
Amicalement,
PS. Afin d'illustrer l'efficacité que peut avoir l'algèbre linéaire dans certains problèmes de la théorie des graphes, voici une preuve du fait que le graphe "triangulaire" $\mathcal K_3\:(n=3,\:k=2)$ est le seul graphe obéissant aux hypothèses du message initial. En conservant les notations précédentes:
$\R^n = \text{Vect}(X) \oplus\text{Ker }E\:\:$ et $\:A$ stabilise chacun des sous-espaces $\text{Vect}(X)$ et $\text{Ker}E$.
Nous avons $AX =kX\:$ et d'autre part: $\:\forall Y \in \text{Ker}E,\:\: A^2Y =(k-1)Y$. Il s'ensuit que toutes les valeurs propres de $A$ sont contenues dans $\{k;\sqrt{k-1};-\sqrt{k-1}\}$. Soient $a,b,c$ les multiplicités respectives de ces valeurs propres. Alors:
$a=1;\:\:\:b,c \in \N;\:\:\: 1+b+c=n;\:\:\: 0 =\text{Tr}A = k +(b-c)\sqrt{k-1}$. On déduit que: $2b = n-1-\dfrac k{\sqrt{k-1}}$ ce qui entraine que $\dfrac k{\sqrt{k-1}}\in \N$ puis que $k=2$.

Re,

Pardon,
Il y a en effet une coquille dans mon dernier message que je corrige: il faut lire $k$ choix possibles pour $y$ ,voisins de $x$ , et non de $s$;
Avec mes excuses,

Pardon @LOU16.
En fait mon contre exemple suppose qu'il existe pour tout $(i, j)$ au plus un $k$ tel que $(i, k)$ et $(j, k)$ soit voisins.
Je vais revoir ça quand j'aurais le temps (j'avais pas relu le 1er message de M65: excuse !).