我有一个图g，它只由星图组成。星图由一个中心节点组成，每个中心节点都有边。设H1，H2，…，Hn是G中存在的不同大小的星图，我们称之为任意星图R的中心的所有节点的集合。
现在假设这些星图是在其他星图上建立边缘，使得在R中的任何节点之间没有边缘发生冲突，那么，如果图应该保持平面，那么R中的节点和不在R的节点之间存在多少个最大的边？
我要这类边数的上界我想到的一个上界是：把它们看作二部平面图，其中r是一组顶点，其余的顶点形成另一组a。我们对这些集（r和a）之间的边感兴趣。因为它是平面二分体，所以这样的边的数目是G中节点数目的两倍。
我的感觉是有一个更好的界限，也许是a中节点数的两倍，加上r中节点数的两倍。
如果你能反驳我的直觉，那也不错。希望你们中的一些人能提出一个很好的范围，以及一些相关的论点。
最佳答案
那是你能做的最好的。取任意平面图G，构造其面顶点关联图H，其面都有4条边设R为G的面集，用H中的边任意构造星，从而得到二部平面图的界。