В чем разница между связностью и многогранностью графа?

Возможно, имелись в виду понятия «связность» и «двудольность» графа, а не «связность» и «многогранность».

Связность графа означает, что между любыми двумя его вершинами есть путь. www.unn.ru www.geeksforgeeks.org Граф называется связным, если в нём только одна компонента связности, то есть если из любой вершины можно пройти в любую, идя по рёбрам. homepage.mi-ras.ru

Двудольность графа заключается в том, что его вершины можно разделить на два непересекающихся множества таким образом, что никакие две вершины в одном множестве не соединены ребром. www.geeksforgeeks.org

Таким образом, связность связана с соединением вершин, а двудольность — с разделением вершин графа на подмножества.