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

An Example of the Bound of Double Tree

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

Abstract: If the graph G contains two spanning trees such that the edges of spanning trees are disjoint. And E(G)=E(T₁)∪E(T₂) and E(T₁)∩E(T₂)=∅ , 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=T₁,T₂ (T₁,T₂ are spanning trees), there exists at least a vertex v∈V(G) such that ▏d_T1(v)-d_T2(v)▏≥2 .