Couper au moins la moitié des arêtes d'un graphe ?

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...