Cреди любых 2d+2 вершин графа можно выбрать d таких, что каждое ребро

Cреди любых 2d+2 вершин графа можно выбрать d таких, что каждое ребро, соединяющее две из этих 2d + 2 вершин, содержит хотя бы одну из выбранных. Докажите, что вершины графа можно раскрасить в d + 1 цвет так, чтобы концы каждого ребра
были разноцветными.