Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
270 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Graphe complémentaire

Envoyé par skan 
Graphe complémentaire
il y a trois années
Soit G =(V,E) un graphe simple.
Démontrer que soit G est connexe, soit G bar est connexe.



Edité 1 fois. La dernière correction date de il y a trois années et a été effectuée par AD.
Re: Graphe complémentaire
il y a trois années
Qu'as-tu essayé ?
Re: Graphe complémentaire
il y a trois années
Bonjour,

J'imagine que ce résultat est très classique et qu'il existe un argument plus simple que celui qui suit. J'ai donc trouvé çà:
Soit $n$ le nombre de sommets du graphe , $s$ (respectivement $t$) le cardinal maximal d'une composante connexe de $G$ (respectivement du complémentaire $\overline{ G}$ de $G$) et enfin $k = \text{max} ( s , t )$.
Si $k < n$ , (on peut choisir, sans perte de généralité, que $ k = s$ ) , alors en notant $C$ une composante connexe de $G$ de cardinal $ k$, et $x$ un sommet hors de $C$, il apparait que $ C \cup \{ x \}$ est inclus dans une composante connexe de $\overline{G}$ de cardinal supérieur ou égal à $k+1$.
C'est impossible et ainsi $k = n$.

Amicalement,



Edité 4 fois. La derni&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par LOU16.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 146 019, Messages: 1 456 792, Utilisateurs: 27 494.
Notre dernier utilisateur inscrit Khass.


Ce forum
Discussions: 845, Messages: 7 096.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page