Théorie des graphes: un seul chemin

[invite56460777]

Bonjour,

J'ai trouvé les propriétés suivantes :
Soit G= (E, K) un graphe,
- si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est, deux noeuds du graph sont toujours reliables par une chaîne.

- Si G n'a pas de boucle,
alors G ne peut être un arbre, que si, pour tous les noeuds, deux noeuds différents peuvent être reliés par une unique chaîne.

Je n'ai aucune idée pour la démonstration de la première propriété. Je voudrais donc quelques conseils.

Pour la deuxième, je pense qu'il faut dire qu'un arbre ne peut pas accepter de cycles. Donc s'il y avait deux chaines, ce ne pourrait être un arbre.
Qqun pourrait-il m'aider à rendre cette démonstration plus cohérente?

Merci d'avance
-----

[martini_bird]

Salut,

Bonjour,
J'ai trouvé les propriétés suivantes :
Soit G= (E, K) un graphe,
- si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est [???], deux noeuds du graph sont toujours reliables par une chaîne.

je cherche le mot manquant: connexe?

[invite8f53295a]

Salut,

Je ne comprends pas très bien ton énoncé. Est-ce
si G est connexe, alors deux noeuds sont toujours reliables par un chaîne ? La connexité étant alors entendue au sens topologique ?

- si chacun des deux noeuds de G peuvent être reliés par une arrête, alors G est, deux noeuds du graph sont toujours reliables par une chaîne.

[invite56460777]

Oui mais comment démontrer la connexité peut se généraliser ?? Je me demande maintenant s'il ne faut pas faire un raisonnement par récurrence.
Pour la deuxième propriété, je trouve ma démonstration un peu légère même si le principe doit être là.

[A voir en vidéo sur Futura]