我有一个仅由星图组成的图G。星形图由一个中心节点组成，该中心节点与其中的每个其他节点都有边。令H 1 , H 2 ,…,H n是G中存在的不同大小的不同星图。我们将所有节点的集合称为任何星图中的中心R。
现在假设这些星图正在构建其他星图的边，使得R中的任何节点之间都没有边。那么，如果图形应该保持平面，则在R中的节点和不在 R 中的节点之间最多存在多少条边？
我想要这样的边缘数量的上限。我想到的一个上限是：将它们视为二分平面图，其中R是一组顶点，其余顶点形成另一组A。我们对这些集合（R和A）之间的边感兴趣。由于它是平面二分的，因此此类边的数量以G中节点数量的两倍为界。
我觉得有一个更好的界限，可能是A中节点数的两倍加上R中的节点数。
如果你能反驳我的直觉，那也很好。希望你们中的一些人可以提出一个很好的界限以及一些相关的论点。