关于双树度差下界的一个例子

An Example of the Bound of Double Tree

如果图G由两个边不交的生成树的并组成,其中E(G)=E(T1)∪E(T2),且E(T1)∩E(T2)=∅那么称图G是双树。本文证明存在一个双树G,对于G任意一个分解f=T1,T2而言(T1,T2是生成树),至少存在一个顶点v∈V(G),使得▏dT1(v)-dT2(v)▏≥2。

If the graph G contains two spanning trees such that the edges of spanning trees are disjoint. And E(G)=E(T1)∪E(T2) and E(T1)∩E(T2)=∅ , then we call the graph G is double tree. In this pa-per we prove that there exists a double tree graph G, for any decomposition f=T1,T2 (T1,T2 are spanning trees), there exists at least a vertex v∈V(G) such that ▏dT1(v)-dT2(v)▏≥2 .