Une île imaginaire dont la carte est représentée ci-dessous, est composée de six provinces, notées A, B, C, D, E et F.
On s'intéresse aux frontières séparant ces provinces. On traduit cette situation par un graphe dont les sommets sont les provinces et où chaque arête représente une frontière entre deux provinces.
On admet que le graphe G ci-dessous représente cette situation :
Donner l'ordre du graphe G, puis le degré de chacun de ses sommets.
Peut-on visiter cette île en franchissant une et une seule fois chacune des dix frontières ? Justifier. Si oui, proposer un parcours possible.
Visiter cette île en franchissant une et une seule fois chacune des dix frontières revient à chercher une chaîne eulérienne.
Le graphe G possède-t-il un sous-graphe complet d'ordre 3 ? Si oui, en citer un.
Préciser, sans justification, si le graphe G possède un sous graphe complet d'ordre 4.
Quelle conséquence cela a-t-il sur le nombre chromatique c du graphe G ?
Proposer une coloration de la carte (ou du graphe) avec le minimum de couleurs afin que deux provinces qui ont une frontière commune aient des couleurs différentes (on peut remplacer les couleurs par différents hachurages).
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.