Koło (teoria grafów)

Przykłady kół

Koło – w teorii grafów, graf powstały z cyklu poprzez dodanie nowego wierzchołka połączonego krawędzią z każdym wierzchołkiem tego cyklu. Koło o $n$ wierzchołkach oznacza się symbolem $W_n$.

Koło o $n$ wierzchołkach jest grafem ostrosłupa o podstawie $(n-1)$-kąta.

Graf $W_n$ ma $n$ wierzchołków i $2(n-1)$ krawędzi. Koło o czterech wierzchołkach jest izomorficzne z grafem pełnym o tej samej liczbie wierzchołków. Z kolei $W_5$ jest izomorficzne z pełnym grafem trójdzielnym $K_{1,2,2}$.

Własności

Koła o nieparzystej liczbie wierzchołków są 3-chromatyczne, a koła o parzystej liczbie wierzchołków mają liczbę chromatyczną równą 4.

Wszystkie koła są planarne. Każde koło jest izomorficzne ze swoim grafem dualnym.

Każde koło jest grafem hamiltonowskim. Co więcej, graf $W_n$ zawiera dokładnie $n-1$ cykli Hamiltona.

Graf $W_7$ jest jedynym kołem, które można narysować na płaszczyźnie tak, aby każda krawędź była jednostkowej długości. Przy zachowaniu tej reguły, pozostałe koła można narysować w przestrzeni trójwymiarowej.

Dla każdego $k,$ wszystkie grafy 3-spójne o odpowiednio wielu wierzchołkach zawierają $W_k$ lub $K_{3,k}$ jako minor.