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

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

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

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