Couper au moins la moitié des arêtes d'un graphe ?
Channel: À la découverte des graphes
Date: 2020-09-03

Coloriez chaque sommet d'un graphe G, soit en rouge, soit vert. Coupez chaque arête qui a une extrémité rouge et une extrémité verte. En vous y prenant bien, pouvez-vous espérer couper ainsi au moins la moitié des arêtes de G ? Réponse dans cette vidéo...