可推出3-NZF的平方图

已知G2=G∪{uv dG(u,v)=2,u,v∈V(G)},如果定义算法,1)令G2=G0,2)Gk=Gk-1\{uv},dG(u,v)=2,这样就可以得到边数更少的图G。考虑G2推出3-NZF但∈τ1,3且|V(G)| |E(G)|的极小反例,以及Gτ1,3但G2不推出3-NZF且满足1.|E(G)|-|V(G)|尽可能小,2.在1)成立的条件下,|E(G)|尽可能小的反例,于是有结论:G2推出3-NZF,当且仅当Gτ1,3。