graf 1: Czy graf którego wierzchołki są reprezentowane przez ciągi binarne długości 5 i dwa wierzchołki są połączone gdy ciągi różnią się na dwóch pozycjach jest grafem dwudzielnym?

kerajs: Zakładam, że taki graf jest dwudzielny. Jeśli do jednego podzbioru należy wierzchołek 0,0,0,0,0, to do drugiego należą wierzchołki o trzech zerach i dwóch jedynkach, w tym wierzchołki 0,0,0,1,1 i 0,0,1,0,1. Niestety wskazana para różni się na dwóch pozycjach, więc połączona jest krawędzią, czyli ten GRAF NIE JEST DWUDZIELNY.

1: dziękuję!