Limiter le nombre d'arêtes entre les graphiques en étoile de sorte que le graphique soit plan

J'ai un graphique qui se compose uniquement de graphiques en étoile. Un graphique en étoile se compose d'un nœud central ayant des arêtes à tous les autres nœuds. Laissez H 1 , H 2 , ... , H n être différents graphiques étoiles de différentes tailles qui sont présents dans G . Nous appelons l'ensemble de tous les nœuds qui sont des centres dans tout graphe étoile R .$G$$H_1, H_2, \ldots, H_n$$G$$R$

Supposons maintenant que ces graphiques étoiles construisent des bords vers d' autres graphiques étoiles de sorte qu'aucun bord est incident entre les noeuds de . Alors, combien d'arêtes existent au maximum entre les nœuds en R et les nœuds qui ne sont pas en R , si le graphe devait rester plan?$R$$R$$R$

Je veux la limite supérieure du nombre de ces bords. Une borne supérieure que j'ai à l' esprit est la suivante : les considérer comme graphe planaire biparti où est un ensemble de sommets et de repos des sommets forment un autre ensemble A . Nous nous intéressons aux arêtes entre ces ensembles ( R et A ). Comme il est bipartite plane, le nombre de ces bords est délimitée par deux fois le nombre de noeuds dans G .$R$$A$$R$$A$$G$

Ce que je ressens est qui est là une meilleure liée, peut - être deux fois les nœuds plus le nombre de noeuds dans R .$A$$R$

Au cas où vous pourriez réfuter mon intuition, ce serait aussi bien. J'espère que certains d'entre vous pourront trouver une bonne limite ainsi que des arguments pertinents.

$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$