Discussion :

[dvp_zero]

Bonjour à tous,

j'aimerai savoir si, en imposant un degré k à chacun des noeuds d'un graphe, cela implique que mon graphe soit k-edge-connected?

Autrement dit, une contrainte sur le degré est une condition nécessire pour le k-edge-connected mais est-elle aussi condition suffisante?

Je n'arrive pas à trouver un contre exemple me montrant un graphe où mes sommets possèdent un degré k et que ce graphe n'est pas k-edge-connected.

Merci beaucoup pour votre aide.

[Franck Dernoncourt]

j'aimerai savoir si, en imposant un degré k à chacun des noeuds d'un graphe, cela implique que mon graphe soit k-edge-connected?

Oui

Autrement dit, une contrainte sur le degré est une condition nécessire pour le k-edge-connected mais est-elle aussi condition suffisante?

Oui

http://mathworld.wolfram.com/k-Edge-ConnectedGraph.html :

The maximum edge connectivity of a given graph is the smallest degree of any node, since deleting these edges disconnects the graph.

[dvp_zero]

Un très grand merci.