Théorie des graphes : k-edge-connected graph

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.

Citation:

---

Envoyé par dvp_zero

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

Citation:

---

Envoyé par dvp_zero

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 :

Citation:

---

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

---

Un très grand merci.