Nouvel exo sur les graphes !

[invite99628bf9]

Bonjour,

Voici un nouvel exercice sur les graphes ! Il ne présente pas de difficulté spécial mais je reste bloqué à la question d), si quelqu'un a une idée ?
Je suis aussi intéressé par la question c) si jamais, je ne suis pas sur de mon raisonnement !

Soient et deux graphes simples. On définit un graphe de la façon suivante : est le produit cartésien de par , et on a

et ou et

a) Dessiner G dans le cas où est et est.
b) Notons (respectivement ) le nombre de sommets (respectivement arêtes) de . Calculer le nombre n (respectivement m) de sommets (respectivement arêtes) de G.
c) Montrer que G est connexe si et seulement si et le sont.
d) Montrer que si  désigne le nombre chromatique de , celui de G est .

D'avance merci !
-----

[invite35452583]

Après une révision du vocabulaire des graphes (j'en avais besoin ) je pense que pour montrer "<=" on peut faire ainsi :
on considère une application fi : Gi->Z/nZ où n=max des nombres chromatiques des Gi où les fi^-1(a) est un stable de Gi pour tout a de Z/nZ.
Si f est définie ainsi sur G1xG2 f(x1,x2)=f1(x1)+f2(x2) alors il me semble que les sous-ensembles f^-1(a) sont des stables pour tout a.

Pour ">=" il me semble qu'il suffit de voir que l'intersection des stables d'une coloration de G1xG2 avec G1x{x2} x2 un élément fixe quelconque de G2 forme une coloration de G1x{x2} qui est "isomorphe" à G1.

[invite99628bf9]

merci pour la réponse !
Mais j'avoue que je ne vois pas trop comment faire pour le moment ! je vais essayer de revoir bien tout ça et si je coince je crierais à la rescousse !
encore merci !

[invite35452583]

Il faut surtout voir que si 2 sommets de G1xG2 sont liés alors ils n'ont pas la même affectation par f car soit les f1(.) soit les f2(.) sont différent alors que les autres sont égaux. Donc les f^(-1)(m+nZ) sont des stables

[A voir en vidéo sur Futura]