В n-мерном кубе имеется 2^n вершин. Если более половины вершин покрашены, то покрашено более 2^(n-1) вершин. Каждая вершина соединена с n другими вершинами ребрами. Следовательно, каждая покрашенная вершина соединена с n другими вершинами ребрами. Таким образом, общее количество ребер, соединенных с покрашенными вершинами, равно n * 2^(n-1). Однако каждое ребро соединяет две вершины, поэтому каждое ребро учитывается дважды. Следовательно, общее количество покрашенных ребер равно (n * 2^(n-1)) / 2 = n * 2^(n-2), что больше или равно n для любого n >= 1. Таким образом, если в n-мерном кубе покрашено более половины вершин, то покрашено не менее n ребер.