Membatasi jumlah tepi antara grafik bintang sehingga grafik itu planar

Saya memiliki grafik yang hanya terdiri dari grafik bintang. Grafik bintang terdiri dari satu simpul pusat yang memiliki tepi ke setiap simpul lain di dalamnya. Mari H 1 , H 2 , ... , H n menjadi grafik bintang yang berbeda dari ukuran yang berbeda yang hadir dalam G . Kami menyebutnya himpunan semua node yang merupakan pusat dalam setiap bintang grafik R .$G$$H_1, H_2, \ldots, H_n$$G$$R$

Sekarang anggaplah grafik bintang ini sedang membangun tepi untuk grafik bintang lain seperti yang ada tepi insiden antara setiap node dalam . Lalu, berapa banyak sisi yang ada maksimum antara node dalam R dan node yang tidak ada dalam R , jika grafik harus tetap planar?$R$$R$$R$

Saya ingin batas atas pada jumlah tepi tersebut. Salah satu batas atas yang saya miliki dalam pikiran adalah: menganggap mereka sebagai graf planar bipartit di mana adalah satu set simpul dan beristirahat dari simpul membentuk lain set A . Kami tertarik tepi antara set ini ( R dan A ). Karena bipartit planar, jumlah tepi tersebut dibatasi oleh dua kali jumlah node dalam G .$R$$A$$R$$A$$G$

Apa yang saya rasakan adalah bahwa ada yang lebih baik terikat, mungkin dua kali node dalam ditambah jumlah node dalam R .$A$$R$

Jika Anda dapat menyangkal intuisi saya, maka itu juga bagus. Semoga beberapa dari Anda dapat menghasilkan ikatan yang baik bersama beberapa argumen yang relevan.

$R$$A$$\ge 2$

$2N-4$$N$$N$$4$

$4$$2N-4$

$4$

$F$$6$$F$$x$$F$$x$$x-a-...-x-b...$$F$$z\neq x$$z$$a$$b$$z$$F$$x-a-y-b-z$$F$$x,y,z$$a,b$$x$$b$$a$$z$$(x,b)$$(a,z)$$F$