Liczba nieizomorficznych grafów o zadanych właściwościach

[achr]

Ile jest nieizomorficznych grafów o 8 wierzchołkach, z których dwa wierzchołki są stopnia 4 i nie są one incydentne, pozostałe wierzchołki są stopnia 3.

Zadanie próbowałem rozwiązać w taki sposób, że rysowałem dwa wierzchołki stopnia czwartego i próbowałem 'łączyć' krawędzie wstawiający między nie 1, 2 lub 3 wierzchołki, a następnie liczyć długość cykli w grafie. Tym sposobem otrzymałem 4 grafy z cyklami o różnych długościach, jednak nie potrafię udowodnić, że to są wszystkie możliwości. Czy istnieje jakiś lepszy sposób na szukanie nieizomorficznych grafów?

[norwimaj]

i próbowałem 'łączyć' krawędzie wstawiający między nie 1, 2 lub 3 wierzchołki,

Trochę nie rozumiem.

Ja te grafy bym posegregował ze względu na liczbę wspólnych sąsiadów obu wyróżnionych wierzchołków. Wtedy dość łatwo jest rozrysować wszystkie możliwości. Jeśli się nie mylę, jest ich \(\displaystyle{ 10}\).

[achr]

Od razu widać, że jednego wspólnego wierzchołka mieć nie mogą, bo to by znaczyło, że wierzchołków wszystkich musi być 9. Ale weźmy np. graf, gdzie mają 2 wspólne wierzchołki, zostają nam 4 wierzchołki stopnia pierwszego i 2 wierzchołki stopnia drugiego. Czy w tym momencie mamy pewność, że łącząc te wierzchołki nie możemy otrzymać więcej nieizomorficznych grafów, chociażby ze względu na długość cykli?

[norwimaj]

Czy w tym momencie mamy pewność, że łącząc te wierzchołki nie możemy otrzymać więcej nieizomorficznych grafów, chociażby ze względu na długość cykli?

To znaczy więcej niż ile?

W przypadku, o którym piszesz (wierzchołki \(\displaystyle{ w_1,w_2}\) stopnia \(\displaystyle{ 4}\) mają dwa wspólne sąsiady \(\displaystyle{ w_3,w_4}\)) możesz rozważyć dwa podprzypadki: \(\displaystyle{ w_3}\) i \(\displaystyle{ w_4}\) są połączone krawędzią albo nie.

\(\displaystyle{ \begin{picture}(0,0)
\multiput(0,0)(-20,10){2}{\multiput(0,0)(20,10){2}{\circle*{3}}}
\put(-32,10){$w_1$}
\put(23,10){$w_2$}
\put(3,-6){$w_3$}
\put(3,22){$w_4$}
\multiput(-10,-20)(20,0){2}{\multiput(0,0)(0,-20){2}{\circle*{3}}}
\multiput(0,0)(20,10){2}{\line(-2,1){20}}
\multiput(0,0)(-20,10){2}{\line(2,1){20}}
\put(-20,10){\line(1,-5){10}}
\put(20,10){\line(-1,-5){10}}
\put(-20,10){\line(1,-3){10}}
\put(20,10){\line(-1,-3){10}}
\end{picture}}\)

W każdym z podprzypadków zastanów się, na ile sposobów można dokończyć rysunek.