Ograniczanie liczby krawędzi między wykresami gwiazdowymi, tak że wykres jest płaski

Mam wykres $G$który składa się tylko z wykresów gwiazd. Wykres gwiezdny składa się z jednego centralnego węzła mającego krawędzie do każdego innego węzła w nim. Pozwolić$H_1, H_2, \ldots, H_n$ być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w $G$. Nazywamy zbiór wszystkich węzłów, które są centrami na dowolnym wykresie gwiazdowym$R$.

Załóżmy teraz, że te wykresy gwiezdne budują krawędzie innych wykresów gwiezdnych, tak że żadna krawędź nie występuje między żadnymi węzłami $R$. Następnie, ile krawędzi istnieje maksymalnie między węzłami w$R$ i węzły, które nie są w $R$, czy wykres powinien pozostać płaski?

Chcę górnej granicy liczby takich krawędzi. Jedną górną granicą, o której myślę, jest: rozważ je jako dwustronny wykres płaski gdzie$R$ jest jednym zestawem wierzchołków, a reszta wierzchołków tworzy inny zestaw $A$. Jesteśmy zainteresowani krawędziami między tymi zestawami ($R$ i $A$). Ponieważ jest to planeta dwustronna, liczba takich krawędzi jest ograniczona dwukrotnością liczby węzłów$G$.

Wydaje mi się, że jest to lepsza granica, może dwa razy więcej węzłów $A$ plus liczba węzłów w $R$.

Gdybyś mógł obalić moją intuicję, byłoby to również dobre. Mam nadzieję, że niektórzy z was wymyślą dobrą więź wraz z kilkoma istotnymi argumentami.

Twoje oświadczenie jest trochę niejednoznaczne: najpierw napisz: „… tak, aby nie było żadnej krawędzi między węzłami w $R$”, ale następny akapit oznacza, że ​​między wierzchołkami nie ma również krawędzi $A$. Zakładam również, że gwiazdy są rozłączne i że policzysz wszystkie krawędzie (w tym te początkowo obecne w gwiazdach). Załóżmy również, że są co najmniej dwie gwiazdki i przynajmniej jedna z nich ma stopień naukowy$\ge 2$.

W takim przypadku nie możesz pokonać $2N-4$ uwiązany ($N$= liczba wszystkich wierzchołków). Rozważ nieco inny scenariusz: zacznij od dowolnego zestawu$N$wierzchołki, niektóre czerwone, niektóre czarne, co najmniej dwa z każdego rodzaju. Na każdym kroku dodaj dowolnie krawędź między czerwonym i czarnym wierzchołkiem, o ile nie tworzy przecięć ani nie powiela się krawędzi. Twierdzę, że kiedy utkniesz, wszystkie cykle mają długość$4$.

Twój scenariusz jest szczególnym przypadkiem tego procesu, w którym najpierw tworzysz gwiazdy, a następnie dodajesz pozostałe krawędzie. Jeśli wszystkie cykle mają długość$4$, $2N-4$związany następuje. Mówiąc bardziej ogólnie, pokazuje, że bez względu na to, od którego dwustronnego wykresu zaczniesz, zawsze możesz uzupełnić go do wykresu czworokątnego (słowo, które stworzyłem).

Pokażmy teraz roszczenie. W tym procesie wszystkie ścieżki będą miały naprzemiennie czarne i czerwone wierzchołki, a każdy cykl będzie miał co najmniej długość$4$. Jeśli wykres nie jest połączony, możesz połączyć dowolny czerwony wierzchołek na zewnętrznej powierzchni jednego komponentu z czarnym wierzchołkiem na drugiej powierzchni innego komponentu. Możemy więc założyć, że wykres jest już podłączony.

Załóżmy, że masz twarz $F$ długości $6$ albo więcej. $F$musi mieć co najmniej trzy czarne wierzchołki (niektóre ewentualnie równe). Jeśli jakiś wierzchołek$x$ powtarza się w dniu $F$, weź dwa kolejne występy zgodnie z ruchem wskazówek zegara z $x$, mówić $x-a-...-x-b...$. $F$ musi zawierać czarny wierzchołek $z\neq x$, więc w zależności od lokalizacji $z$, moglibyśmy się połączyć $a$ lub $b$ do $z$ wewnątrz $F$bez powielania krawędzi. Jeśli żaden wierzchołek się nie powtórzy, wybierz sekcję zgodną z ruchem wskazówek zegara$x-a-y-b-z$ z $F$, gdzie $x,y,z$ są czarne i $a,b$są czerwone. Gdyby$x$ jest połączony z $b$ następnie $a$ nie można połączyć się z $z$ (przez płaskość), dzięki czemu możemy dodać jedną z krawędzi $(x,b)$, $(a,z)$ wewnątrz $F$.