Разница между двудольным и полным графами заключается в характере соединений вершин.

Полный граф — это граф, в котором каждая вершина соединена ребром с каждой другой вершиной. 1 Такой граф содержит все возможные для своего типа рёбра при неизменном множестве вершин. 2

Двудольный граф — это граф, в котором вершины можно разделить на две группы так, что рёбра будут соединять только вершины из разных групп. 1 То есть внутри одной группы вершины не соединены рёбрами. 1

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