The 2-Factor Polynomial Detects Even Perfect Matchings
Scott Baldridge Adam M. Lowrance Ben McCarty




[
    [
    December 30, 2023
=====================




In this paper, we prove that the 2-factor polynomial, an invariant of a planar trivalent graph with a perfect matching, counts the number of 2-factors that contain the perfect matching as a subgraph. Consequently, we show that the polynomial detects even perfect matchings.  







§ INTRODUCTION


In <cit.>, the first author developed a cohomology theory of a planar trivalent graph equipped with a perfect matching, and observed that the graded Euler characteristic of that cohomology is a polynomial invariant called the 2-factor polynomial.  Given  a planar trivalent graph G with a perfect matching M, a perfect matching drawing Γ for the pair (G,M) is a topological embedding of the graph in the 2-sphere that marks the perfect matching edges.  We define the 2-factor bracket of the perfect matching drawing, written ⟨Γ⟩_2 as the Laurent polynomial in the variable z calculated recursively on immersed perfect matching drawings by the relations in Figure <ref>.




The bold edge in Figure <ref> represents a perfect matching edge (the only edges to which we apply the bracket), and the circle represents any immersed circle with no vertices.  

In  Section 3 of <cit.>, it was shown that the 2-factor polynomial is independent of the choice of perfect matching drawing, and thus is an invariant of planar trivalent graphs equipped with a perfect matching, i.e., the pair (G,M).  Thus we can define the 2-factor polynomial of the pair (G,M) to be the 2-factor bracket of the perfect matching drawing Γ.

    ⟨ G : M ⟩_2(z) = ⟨Γ⟩_2(z).


The bracket relations in Figure <ref> give a recursive method for computing the 2-factor polynomial. For example, the 2-factor polynomial of the θ graph with perfect matching is:


    ⟨-0.43
        < g r a p h i c s >
    ⟩_2   =   ⟨-0.43
        < g r a p h i c s >
    ⟩_2 -z ⟨-0.43
        < g r a p h i c s >
    ⟩_2
       =    (z^-1+z)^2 - z(z^-1+z)
       =    z^-2+1.


The polynomial depends on both the graph and the perfect matching.  To see this dependence, we compute the 2-factor polynomial of the 3-prism, or circular ladder, denoted P_3, for each of the perfect matchings in Figure <ref>.  




The calculation of these examples also serve as a way to introduce the cube of resolutions, which we will use throughout this paper (cf. <cit.>).  Briefly, to construct a cube of resolutions for (P_3,L), first resolve each perfect matching of the graph into one of the two resolutions shown in the first equation of Figure <ref> to get a state.  Next, order the states into columns from left-to-right by the number of “cross-resolutions”  in each state.  Finally, draw an arrow from a state in one column to a state in the adjacent column to the right if the two states are related by replacing one “open-resolution” )( with one cross-resolution .  The cube of resolutions for (P_3,L) is given in Figure <ref>.



To calculate the polynomial, note that each state contributes a term of the form (-z)^k(z+z^-1)^ℓ where k is the number of cross-resolutions  and ℓ is the number of immersed circles in the state.   From Figure <ref>, we can calculate the polynomial of (P_3,L) directly to see that 

    ⟨ P_3 : L ⟩_2(z)      = (z+z^-1)^3 - 3z (z+z^-1)^2 + 3z^2 (z+z^-1) - z^3 (z+z^-1) 
        = z^-3 - z^2+z^3-z^4.





On the other hand, Figure <ref> shows the cube of resolutions for (P_3,C), and hence, we can calculate the polynomial directly to see that 

    ⟨ P_3 : C ⟩_2(z) = z^-2 - z^-1 + 1 + z^3.

The polynomials for the two perfect matchings are different, and therefore the perfect matchings are different.  The polynomials depend upon the perfect matching. It is the goal of this paper to partially characterize that dependence.

The 2-factor polynomial incorporates some of the most interesting results to  come out of knot theory in the past thirty years together with  counting techniques important to graph theory.  By evaluating the polynomials at 1, we see that ⟨ P_3 : L ⟩_2(1)=0 and ⟨ P_3 : C ⟩_2(1)=2.  The main theorem of this paper says that these numbers are the count of 2-factors that contain  L and C respectively.  To describe the main theorem, we need to introduce some notions related to factorability.  

Recall that a k-factor of G is a spanning k-regular subgraph of G.  For example, the vertex set V(G) is a 0-factor, and a perfect matching (with vertices) is a 1-factor.  A 2-factor is a disjoint set of a cycles that span the vertex set.  When G is also regular, it is natural to count the number of k-factors “between” an ℓ-factor M of G and G, i.e., the index of k-factors that contain M and are contained in G.  


Given an n-regular graph G and an ℓ-factor M of G, then a k-factor K factors through M if M is a subgraph of K. Denote the set of all k-factors of G that factor through M by [G:M].  For a specific k, denote the set of all k-factors of G that factor through M by [G:M]_k and denote the number of elements of [G:M]_k by the index |G:M|_k.


Our main theorem in this paper proves Conjecture 1.2 of <cit.> and says that the 2-factor polynomial counts the number of 2-factors that factor through the perfect matching:



Let G be a planar trivalent graph with perfect matching M. Evaluating the 2-factor polynomial of (G,M) at 1 counts the number of elements of [G:M]_2, i.e.,

    ⟨ G:M⟩_2(1) = |G:M|_2.



Looking back at the circular ladder examples, one can check by hand that |P_3 : L|_2 = 0, while |P_3 : C|_2 = 2, just as the theorem says.  Moreover, notice that in this example, P_3 ∖ L has two 3-cycles, while P_3∖ C contains a single 4-cycle.  (Here and throughout we think of a 1-factor as either a subgraph or a set of perfect matching edges, depending on context.) 

The graph G∖ M is always a set of disjoint cycles {C_1, C_2, …, C_k}, and  the number of edges in each C_i provides important information about |G:M|_2.  Consider one of these cycles, C_i, and note that every cycle of a 2-factor that factors through M must enter C_i through a perfect matching edge of M and then leave C_i through a different perfect matching edge of M. Thus, any 2-factor that factors through M must span an even number of vertices of C_i.  If any cycle C_i in G∖ M has an odd number of edges, i.e., if C_i is an odd cycle, then |G:M|_2 = 0. 

On the other hand, if C_i has an even number of edges for all i, then every 2-factor that factors through M consists of M and a perfect matching for each C_i.  This is because every other edge of C_i must be included in the 2-factor.   Since each C_i has two perfect matchings, there are 2^k choices.  Thus we obtain the following:



Let G be a connected planar trivalent graph with perfect matching M such that G∖ M is a set of k disjoint cycles. If any cycle in this set is odd, then |G:M|_2=0. If all cycles are even, then |G:M|_2= 2^k.



Theorem <ref> and Propostion <ref> taken together imply that the 2-factor polynomial is 0 whenever the graph G∖ M contains a cycle with an odd number of edges, and it is a power of two precisely when all cycles are even. Thus we immediately obtain:



Let G be a planar trivalent graph with perfect matching
M. If any of the cycles in G(V, E ∖ M) have an odd number of edges, then the 2-factor polynomial
for (G, M) satisfies

    ⟨G:M⟩_2(1)=0.

In particular, if ⟨G:M⟩_2 (1) > 0 for the pair (G,M), then M is an even perfect matching of G.


The existence of an even perfect matching for a planar trivalent graph implies that there is a Tait coloring for the graph, i.e., it is 3-edge colorable (cf. <cit.>).  In fact, Theorem <ref>  implies more. Pick three colors {i,j,k} to label edges. By Theorem <ref>, ⟨G:M⟩_2(1) counts the number of 2-factors that factor through M.  For each such 2-factor, label the perfect matching edges of the 2-factor by i and the remaining edges of the 2-factor by j.  Label the edges in the complement of the 2-factor by k.  Thus, ⟨G:M⟩_2(1) counts the number of Tait colorings of G where the edges of M are colored by i. Thus, summing up over all perfect matchings counts the total number of Tait colorings of G.  This motivates the  definition:

 Let G be a connected planar trivalent graph.  Define the planar Tait polynomial of G to be

    T_G(z) = ∑_M∈[G:V(G)]_1⟨ G:M ⟩_2(z).



(Recall that [G:V(G)]_1 is the set of all 1-factors of G.) The polynomial T_G is an invariant of G (cf.  <cit.>).  In particular, one can prove the following about T_G:


If G is a connected planar trivalent graph, then T_G(1) counts the number of Tait colorings of G, i.e.,

    T_G(1) = #|Tait colorings of G|.



For example, the theta graph θ has three perfect matchings, one for each edge of the graph.  The 2-factor polynomial is the same for each perfect matching, thus

    T_θ(z)= 3z^-2+3.

 There are six Tait colorings of the θ graph, and the above computation of T_θ(z) implies T_θ(1)=6.

Another example that we can calculate is P_3.  There is one perfect matching corresponding to the ladder L and three perfect matchings corresponding to C and two 120^∘ rotations of C. Therefore, 

    T_P_3(z)=(z^-3-z^2+z^3-z^4)+3(z^-2-z^-1+1+z^3),

and T_P_3(1)=6, which is the number of Tait colorings of P_3. Note that the perfect matching L does not contribute any colorings.


A planar trivalent graph G has a Tait coloring if and only if its faces are 4-colorable (cf. <cit.>, <cit.>, <cit.>). Hence, the four color theorem <cit.> is equivalent to the following theorem. For other examples of results equivalent to the four color theorem, see <cit.> and <cit.>.



If G is a connected, bridgeless, planar trivalent graph, then T_G(1)>0.


The planar Tait polynomial is a sum of 2-factor polynomials. It is the authors' hope that the 2-factor polynomial or its categorification from <cit.> may shed light on the number of Tait colorings of a connected planar trivalent graph.




§ PRELIMINARIES


The proof of Theorem <ref> rests upon the use of IH-moves to transform a given bridgeless, planar trivalent graph with a perfect matching (G,M) into one where we know Theorem <ref> holds.   



An IH-move is a local replacement of the configuration shown on the left in Figure <ref> with the one shown on the right.






Note that we only perform an IH-move on a perfect matching edge.



Given two graphs, G and G', and perfect matchings for each M and M' respectively, we say that (G,M) is IH-equivalent to (G',M') if there is a sequence of IH-moves taking one to the other.


Before we proving the main theorem, we need to establish a series of lemmas about IH-moves. 





The 2-factor polynomial and the number of 2-factors of G that factor through M satisfy the following IH-relations:


[thick, scale = .8, baseline=(current bounding box.center)][ultra thick] (0,0) – (0,1);
(0,0) circle (3pt);
(0,1) circle (3pt);
(-.4,-.2) – (0,0) – (.4,-.2);
(-.4,1.2) – (0,1) – (.4,1.2);
(-.4,-.4) – (-.8,.5) – (-.4,1.4);
(.4,-.4) – (.8,.5) – (.4,1.4);
(.7,-.3) node2;
     -      
[thick, scale = .8, baseline=(current bounding box.center)](-0.5,.9) – (-0.3,.5) – (-0.5,.1);
(-0.3,.5) circle (3pt);
(0.7,.5) circle (3pt);
[ultra thick] (-0.2,.5) – (0.8,.5);
(0.9,.9) – (0.7,.5) – (0.9,.1);
(-.4,-.4) – (-.8,.5) – (-.4,1.4);
(.8,-.4) – (1.2,.5) – (.8,1.4);
(1.1,-.3) node2;
    =      
[thick, scale = .8, baseline=(current bounding box.center)]
[white!70!black] (.12,.6) to 
	(-.12,.6) to [out = -60, in = 90] 
	(-.1,.5) to [out = -90, in = -120] 
	(-.12,.4) to 
	(.12,.4) to [out = 120, in = -90]
	(.1,.5) to [out = 90, in = -120]
	(.12,.6);
	(-.4,-.4) – (-.8,.5) – (-.4,1.4);
	(.4,-.4) – (.8,.5) – (.4,1.4);
	(.7,-.3) node2;
	(-.4,-.2) to [out = 60, in = -90] (-.1,.5) to [out = 90, in = -60] (-.4,1.2);
	(.4,-.2) to [out = 120, in = -90] (.1,.5) to [out = 90, in = -120] (.4,1.2);
    -       
[thick, scale = .8, baseline=(current bounding box.center)](-.6,-.4) – (-1,.5) – (-.6,1.4);	
	[white!70!black] 
	(.1,.6) to (-.1,.6) to (-.1,.4) to 
	(.1,.4) to (.1,.6);
	(-.7,0.9) to [out = -30, in = 180] (0,.6) to [out = 0, in = 210] (0.7,0.9);
	(-.7,0.1) to [out = 30, in = 180] (0,0.4) to [out = 0, in = 150] (0.7,0.1);
	(.6,-.4) – (1,.5) – (.6,1.4);
	(.9,-.3) node2;



[thick, scale = .8, baseline=(current bounding box.center)]
[ultra thick] (0,0) – (0,1);
(0,0) circle (3pt);
(0,1) circle (3pt);
(-.4,-.2) – (0,0) – (.4,-.2);
(-.4,1.2) – (0,1) – (.4,1.2);
(-.5,-.4) – (-.5,1.4);
(.5,-.4) – (.5,1.4);
(.8,-.3) node2;
    -     
[thick, scale = .8, baseline=(current bounding box.center)](-0.5,.9) – (-0.3,.5) – (-0.5,.1);
(-0.3,.5) circle (3pt);
(0.7,.5) circle (3pt);
[ultra thick] (-0.2,.5) – (0.8,.5);
(0.9,.9) – (0.7,.5) – (0.9,.1);
(-.6,-.4) – (-.6,1.4);
(1,-.4)  – (1,1.4);
(1.3,-.3) node2;
   =      
[thick, scale = .8, baseline=(current bounding box.center)][white!70!black] (.12,.6) to 
	(-.12,.6) to [out = -60, in = 90] 
	(-.1,.5) to [out = -90, in = -120] 
	(-.12,.4) to 
	(.12,.4) to [out = 120, in = -90]
	(.1,.5) to [out = 90, in = -120]
	(.12,.6);
	(-.5,-.4) – (-.5,1.4);
	(.5,-.4) – (.5,1.4);
	(.8,-.3) node2;
	(-.4,-.2) to [out = 60, in = -90] (-.1,.5) to [out = 90, in = -60] (-.4,1.2);
	(.4,-.2) to [out = 120, in = -90] (.1,.5) to [out = 90, in = -120] (.4,1.2);
   -     
[thick, scale = .8, baseline=(current bounding box.center)]	(-.8,-.4) – (-.8,1.4);
	[white!70!black] 
	(.1,.6) to (-.1,.6) to (-.1,.4) to 
	(.1,.4) to (.1,.6);
	(-.7,0.9) to [out = -30, in = 180] (0,.6) to [out = 0, in = 210] (0.7,0.9);
	(-.7,0.1) to [out = 30, in = 180] (0,0.4) to [out = 0, in = 150] (0.7,0.1);
	(.8,-.4) – (.8,1.4);
	(1.1,-.3) node2;
	






Observe that the first equation in Figure <ref> remains true when each term is rotated 90 degrees, as shown below. This new relation, subtracted from the the first equation in Figure <ref> yields Equation <ref>.  



    [thick, scale = .8]
    	
    
    [yshift = -2 cm]
    
    
    
    [xshift = -0.3cm]
     (-0.5,.9) – (-0.3,.5) – (-0.5,.1);
     (-0.3,.5) circle (3pt);
     (0.7,.5) circle (3pt);
     [ultra thick] (-0.2,.5) – (0.8,.5);
     (0.9,.9) – (0.7,.5) – (0.9,.1);
    
     (-.4,-.4) – (-.8,.5) – (-.4,1.4);
     (.8,-.4) – (1.2,.5) – (.8,1.4);
     (1.1,-.3) node2;
    
     (1.5, .5) node=;
    
    
    
    [xshift = 3.3 cm]
    
    	 (-.6,-.4) – (-1,.5) – (-.6,1.4);
    	
    	[white!70!black] 
    	(.1,.6) to (-.1,.6) to (-.1,.4) to 
    	(.1,.4) to (.1,.6);
    
    	 (-.7,0.9) to [out = -30, in = 180] (0,.6) to [out = 0, in = 210] (0.7,0.9);
    	 (-.7,0.1) to [out = 30, in = 180] (0,0.4) to [out = 0, in = 150] (0.7,0.1);
    
    	 (.6,-.4) – (1,.5) – (.6,1.4);
    	 (.9,-.3) node2;
    	
    	
     (5, .5) node-;
     (5.5,.5) nodez;
    
    
    [xshift = 6.5 cm]
    	 (-.4,-.4) – (-.8,.5) – (-.4,1.4);
    	 (.4,-.4) – (.8,.5) – (.4,1.4);
    	 (.7,-.3) node2;
    	 (-.4,-.2) – (.4,1.2);
    	 (-.4,1.2) – (.4,-.2);



The index |G:M|_2 of 2-factors that factor through M satisfies the same IH-relation (Equation <ref>). Label the four pictures of Equation <ref> from left to right by (G_i,M_i) for i=1, 2 , 3, and 4. Suppose that the non-perfect matching edges  in (G_1,M_1) are part of the same cycle C_1 in G_1(V_1,E_1∖ M_1) as in Figure <ref>.  The non-perfect matching edges of the second picture of Equation <ref> will then be parts of two different cycles C_2 and C_2 in G_2(V_2,E_2∖ M_2), and so on as displayed in Figure <ref>. Let C_4 be the cycle corresponding to C_1 in the fourth picture. Clearly the number of cycles in G_1∖ M_1 is equal to the number of cycles in G_4 ∖ M_4, and since C_4 has two fewer edges than C_1, both cycles have the same parity.  Therefore, by Proposition <ref>, |G_1:M_1|_2 = |G_4:M_4|_2. 





Suppose that C_2 and C_2 have k and k edges respectively. The corresponding cycles C_3 and C_3 have k-1 and k-1 edges respectively. If both k and k are even, then k-1 and k-1 are odd, implying that |G_3:M_3|_2=0. Also, in this case, |G_2:M_2|_2=2|G_1:M_1|_2.  Thus, Equation <ref> is satisfied. If exactly one of k and k is odd, then all four terms of Equation <ref> are zero. If both k and k are odd, then |G_2:M_2|_2=0 and |G_3:M_3|_2= 2|G_1:M_1|_2, and Equation <ref> is again satisfied. 

Finally, if the non-perfect matching edges in the first picture of Equation <ref>  lie in two different cycles in G_1(V_1,E_1∖ M_1), then the non-perfect matching edges in second picture of Equation <ref> must be part of one cycle. Thus, the argument for this case is the same as the previous case with the pictures reversed.





The 2-factor polynomial, when evaluated at 1, and the index of 2-factors that factor through M both satisfy the following bubble relation:



    [scale = 0.7]
    [xshift= 0cm]
    
    [ultra thick] (0,-0.5) – (0,0.25);
    [ultra thick] (0,0.75) – (0,1.5);
    
     (0,-0.5) circle (3pt);
     (0,1.5) circle (3pt);
     (0,0.25) circle (3pt);
     (0,0.75) circle (3pt);
    
     (0,0.5) circle (0.25 cm);
     (-.4,-.7) – (0,-0.5) – (.4,-.7);
     (-.4,1.7) – (0,1.5) – (.4,1.7);
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    
     (1.75, .5) node =;
     (2.25,0.5) node 2;
    
    [xshift= 3.25 cm]
    
    [ultra thick] (0,0) – (0,1);
     (0,0) circle (3pt);
     (0,1) circle (3pt);
     (-.4,-.2) – (0,0) – (.4,-.2);
     (-.4,1.2) – (0,1) – (.4,1.2);
     (-.4,-.4) – (-.8,.5) – (-.4,1.4);
     (.4,-.4) – (.8,.5) – (.4,1.4);
     (.7,-.3) node2;
    
    
     (1.1,0.5) node(1);
    
    
    [yshift = -3 cm, xshift= 0cm]
    
    [ultra thick] (0,-0.5) – (0,0.25);
    [ultra thick] (0,0.75) – (0,1.5);
    
     (0,-0.5) circle (3pt);
     (0,1.5) circle (3pt);
     (0,0.25) circle (3pt);
     (0,0.75) circle (3pt);
    
     (0,0.5) circle (0.25 cm);
     (-.4,-.7) – (0,-0.5) – (.4,-.7);
     (-.4,1.7) – (0,1.5) – (.4,1.7);
     (-.5,-.9) – (-.5,1.9);
     (.5,-.9) – (.5,1.9);
     (.7,-.8) node2;
    
    
    
     (1.75, .5) node =;
     (2.25,0.5) node 2;
    
    [ xshift= 3 cm]
    
    [ultra thick] (0,0) – (0,1);
     (0,0) circle (3pt);
     (0,1) circle (3pt);
     (-.4,-.2) – (0,0) – (.4,-.2);
     (-.4,1.2) – (0,1) – (.4,1.2);
     (-.5,-.4) – (-.5,1.4);
     (.5,-.4) – (.5,1.4);
     (.7,-.3) node2;




The relationship for the index of 2-factors that factor through M follows immediately from Proposition <ref>. The proof of the bubble lemma for the 2-factor polynomial is given by resolving the perfect matchings as in the picture below:



    [scale=0.75]
    [xshift= 0cm]
    
    
    [ultra thick] (0,-0.5) – (0,0.25);
    [ultra thick] (0,0.75) – (0,1.5);
    
     (0,-0.5) circle (3pt);
     (0,1.5) circle (3pt);
     (0,0.25) circle (3pt);
     (0,0.75) circle (3pt);
    
     (0,0.5) circle (0.25 cm);
     (-.4,-.7) – (0,-0.5) – (.4,-.7);
     (-.4,1.7) – (0,1.5) – (.4,1.7);
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    
     (1.75, .5) node =;
    
    [xshift = 3.25 cm]
    [white!70!black] (.11,1.35) to 
    	(-.11,1.35) to [out = -60, in = 90] 
    	(-.1,1.25) to [out = -90, in = -120] 
    	(-.11,1.15) to 
    	(.11,1.15) to [out = 120, in = -90]
    	(.1,1.25) to [out = 90, in = -120]
    	(.11,1.35);
    	
    [ultra thick] (0,-0.5) – (0,0.25);
    
     (0,-0.5) circle (3pt);
     (0,0.25) circle (3pt);
    
     (0,0.25) to [out = 95, in = 270] (-0.2,0.75);
     (-0.2,0.75) to [out = 90, in = 270] (-0.1,1.25);
     (-0.1,1.25) to [out = 90, in = 290] (-0.3,1.75);
    
     (0,0.25) to [out = 85, in = 270] (0.2,0.75);
     (0.2,0.75) to [out = 90, in = 270] (0.1,1.25);
     (0.1,1.25) to [out = 90, in = 250] (0.3,1.75);
    
     (-.4,-.7) – (0,-0.5) – (.4,-.7);
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
    
    
    	
     (1.1,0.5) node(1);
    
     (5,0.5) node-;
    
    
    [xshift = 6.5 cm]
    [ultra thick] (0,-0.5) – (0,0.25);
    
     (0,-0.5) circle (3pt);
     (0,0.25) circle (3pt);
    
     (0,0.25) to [out = 95, in = 270] (-0.2,0.75);
     (-0.2,0.75) to [out = 90, in = 250] (0.3,1.75);
    
     (0,0.25) to [out = 85, in = 270] (0.2,0.75);
     (0.2,0.75) to [out = 90, in = 290] (-0.3,1.75);
    
     (-.4,-.7) – (0,-0.5) – (.4,-.7);
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    [yshift = -3 cm]
    
    
     (1.75, .5) node =;
    
    [xshift = 3.25 cm]
    [white!70!black] 
    	(.11,1.15 + 0.1) 
    	to (-.11,1.15 + 0.1) to (-.11,1.15 - 0.1) 
    	to (.11,1.15 - 0.1) to (.11,1.15 +0.1);
    	
    	[white!70!black] 
    	(.11,-0.15 + 0.1) 
    	to (-.11,-0.15 + 0.1) to (-.11,-0.15 - 0.1) 
    	to (.11,-0.15 - 0.1) to (.11,0.15 +0.1);
    	
    
     (-0.3,-0.8) 
    to [out = 70, in = 270] (-0.1,-0.8 + 0.65)
    to [out = 90, in = 270] (-0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 270] (-0.1,-0.8 + 3*0.65)
    to [out = 90, in = 290] (-0.3,-0.8 + 4*0.65);
    
     (0.3,-0.8) 
    to [out = 110, in = 270] (0.1,-0.8 + 0.65)
    to [out = 90, in = 270] (0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 270] (0.1,-0.8 + 3*0.65)
    to [out = 90, in = 250] (0.3,-0.8 + 4*0.65);
    
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    
     (5,0.5) node-;
    
    
    [xshift = 6.5 cm]
    
    	[white!70!black] 
    	(.11,1.15 + 0.1) 
    	to (-.11,1.15 + 0.1) to (-.11,1.15 - 0.1) 
    	to (.11,1.15 - 0.1) to (.11,1.15 +0.1);
    	
     (0.3,-0.8) 
    to [out = 110, in = 290] (0,-0.8 + 0.65)
    to [out = 110, in = 270] (-0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 270] (-0.1,-0.8 + 3*0.65)
    to [out = 90, in = 290] (-0.3,-0.8 + 4*0.65);
    
     (-0.3,-0.8) 
    to [out = 70, in = 250] (0,-0.8 + 0.65)
    to [out = 70, in = 270] (0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 270] (0.1,-0.8 + 3*0.65)
    to [out = 90, in = 250] (0.3,-0.8 + 4*0.65);
    
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    
     (8.3,0.5) node-;
    
    
    [xshift = 9.8 cm]
    
    	[white!70!black] 
    	(.11,-0.15 + 0.1) 
    	to (-.11,-0.15 + 0.1) to (-.11,-0.15 - 0.1) 
    	to (.11,-0.15 - 0.1) to (.11,0.15 +0.1);
    		
     (0.3,-0.8 + 4*0.65) 
    to [out = 250, in = 70] (0,-0.8 + 3*0.65)
    to [out = 70, in = 90] (-0.2,-0.8 + 2*0.65 ) 
    to [out = 270, in = 90] (-0.1,-0.8 + 0.65)
    to [out = 270, in = 70] (-0.3,-0.8);
    
     (-0.3,-0.8 + 4*0.65) 
    to [out = -70, in = 110] (0,-0.8 + 3*0.65)
    to [out = -70, in = 90] (0.2,-0.8 + 2*0.65 ) 
    to [out = 270, in = 90] (0.1,-0.8 + 0.65)
    to [out = 270, in = 110] (0.3,-0.8);
    
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    
     (11.5,0.5) node+;
    
    
    [xshift = 12.9 cm]
    	
     (0.3,-0.8) 
    to [out = 110, in = 290] (0,-0.8 + 0.65)
    to [out = 110, in = 270] (-0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 250] (0,-0.8 + 3*0.65)
    to [out = 70, in = 250] (0.3,-0.8 + 4*0.65); 
    
     (-0.3,-0.8) 
    to [out = 70, in = 250] (0,-0.8 + 0.65)
    to [out = 70, in = 270] (0.2,-0.8 + 2*0.65 ) 
    to [out = 90, in = 290] (0,-0.8 + 3*0.65)
    to [out = 110, in = 290] (-0.3,-0.8 + 4*0.65); 
    
     (-.4,-.9) – (-.8,.5) – (-.4,1.9);
     (.4,-.9) – (.8,.5) – (.4,1.9);
     (.7,-.8) node2;
    
     (1.1,0.5) node(1);
    [yshift = -5.5 cm]
    
    
    
     (1.75, .5) node =;
    
    
    [xshift = 3.25 cm]
    	 (-1,.5) node2;
    	[white!70!black] (.12,.6) to 
    	(-.12,.6) to [out = -60, in = 90] 
    	(-.1,.5) to [out = -90, in = -120] 
    	(-.12,.4) to 
    	(.12,.4) to [out = 120, in = -90]
    	(.1,.5) to [out = 90, in = -120]
    	(.12,.6);
    	 (-.4,-.4) – (-.8,.5) – (-.4,1.4);
    	 (.4,-.4) – (.8,.5) – (.4,1.4);
    	 (.7,-.3) node2;
    	 (-.4,-.2) to [out = 60, in = -90] (-.1,.5) to [out = 90, in = -60] (-.4,1.2);
    	 (.4,-.2) to [out = 120, in = -90] (.1,.5) to [out = 90, in = -120] (.4,1.2);
    	 (1.1,0.5) node(1);
    	
     (5, .5) node-;
     (5.5,.5) node2;
    
    
    [xshift = 6.5 cm]
    	 (-.4,-.4) – (-.8,.5) – (-.4,1.4);
    	 (.4,-.4) – (.8,.5) – (.4,1.4);
    	 (.7,-.3) node2;
    	 (-.4,-.2) – (.4,1.2);
    	 (-.4,1.2) – (.4,-.2);
    	 (1.1,0.5) node(1);
    
    [yshift = -7.5 cm, xshift= 3.25 cm]
    
     (-1.5, .5) node =;
    
    
    	 (-1,.5) node2;
    [ultra thick] (0,0) – (0,1);
     (0,0) circle (3pt);
     (0,1) circle (3pt);
     (-.4,-.2) – (0,0) – (.4,-.2);
     (-.4,1.2) – (0,1) – (.4,1.2);
     (-.4,-.4) – (-.8,.5) – (-.4,1.4);
     (.4,-.4) – (.8,.5) – (.4,1.4);
     (.7,-.3) node2;
    
    
     (1.1,0.5) node(1);








Note that the bubble relation in Lemma <ref> is not true of the polynomial itself, just the value of the polynomial when evaluated at 1.  




Let G be a connected planar trivalent graph with a perfect matching M.  If G contains a bridge, then ⟨ G : M⟩_2(1) = 0, and |G:M|_2 = 0.  



The result  for |G:M|_2 follows from Proposition <ref>. For the 2-factor polynomial, first note that if G has a bridge, then it must be a perfect matching edge (cf. <cit.>). Resolving this perfect matching edge shows that the 2-factor polynomial has a (z-1) factor, and therefore ⟨G:M⟩_2(1)=0 (again, see <cit.>).









Let the pair (G,M) be a planar trivalent graph G with perfect matching M.  If  G(V,E∖ M) is a single cycle, then G must contain one of the local configurations appearing to the left of each arrow in Figure <ref>.



Suppose that M has k edges, and that G has n vertices (n=2k). Since G(V,E∖ M) is a cycle, it has an inside and an outside. Either the inside or outside of C contains at least k/2 edges of the perfect matching M. Without loss of generality, assume the inside of C contains at least k/2 edges of M. Call this inside region D.  Since at least k/2 edges of M lie in D, those edges split D into at least 1 + k/2 disk faces.  The boundary of each of these disks will contain some number of edges of M, and some number of vertices that do not belong to any edge of M.  If such a disk has m edges from M and ℓ vertices not incident to any edge of M on the inside of the cycle C, then we label that disk D^ℓ_m. The configurations in Figure <ref> are D_1^0, D_1^1, D_1^2, D_2^0, D_2^1 and D_3^0. By way of contradiction, assume no such configuration appears in D.

We form another graph T by placing a vertex in each face of D and joining two vertices when their associated faces are separated by an edge of M. The graph T is a tree, and the degree of each vertex in T is the number of perfect matching edges M in the boundary of that disk face. Let δ_m denote the number of faces of the form D_m^ℓ for any ℓ. Hence δ_m is the number of degree m vertices in the tree T. A standard way to count leaves in a tree results in the following formula:

    δ_1 = 2 + ∑_m=3^∞ (m-2)δ_m.


Define δ_≥ 4 = ∑_m=4^∞δ_m. The above equality implies that δ_1 ≥ 2 + δ_3 + 2δ_≥ 4, or equivalently that δ_≥ 4≤1/2(δ_1 - δ_3)-1. Therefore
 
    k/2+1 ≤δ_1 + δ_2 + δ_3 + δ_≥ 4≤3δ_1/2 + δ_2 + δ_3 /2-1,

 or
 
    k ≤ 3δ_1 +2δ_2 + δ_3 - 4.


Since the faces in Figure <ref> are assumed not to appear in C, each disk of the form D_1^ℓ must have ℓ≥ 3, each disk of the form D_2^ℓ must have ℓ≥ 2, and each disk of the form D_3^ℓ must have ℓ≥ 1. There are also at most k vertices of G not incident to an edge of the matching M inside C. By counting the number of vertices of G not incident to an edge of the matching M inside C, we obtain the inequality 

    k ≥ 3δ_1 + 2δ_2 + δ_3.

Therefore

    k ≥ 3δ_1 + 2δ_2 + δ_3>3δ_1 +2δ_2 + δ_3 - 4 ≥ k.

Having arrived at a contradiction, we conclude that some face from Figure <ref> appears in C.




Let G be a connected bridgeless planar trivalent  graph with perfect matching M. There exists a sequence of IH-moves transforming the pair (G,M) into the pair (G',M') where G' is a planar trivalent bridgeless graph and M' is a perfect matching of G' such that G'(V',E'∖ M') contains a cycle of length at most three.


An IH-move either merges or splits two cycles of G(V,E∖ M). In a connected graph where G(V,E∖ M) contains more than one cycle, one can perform an IH-move that merges two cycles of G(V,E∖ M). Thus there is a sequence of IH-moves transforming (G,M) into the pair (G_1,M_1) such that G_1(V_1,E_1∖ M_1) is a single cycle C. 

Lemma <ref> implies that a face as in Figure <ref> must appear either inside or outside of the cycle C in G_1. Performing the IH-move(s) in Figure <ref> to the appropriate edge(s) of M_1 results in a pair (G',M') such that G'(V',E'∖ M') contains a cycle of length at most three.




Let G be a planar trivalent graph G with a perfect matching M.  If G∖ M contains a 3-cycle, then ⟨G:M⟩_2(1)  = 0.



Assume that M has k edges and G has n vertices (n=2k). Observe that if 2 vertices of the cycle are also connected by a perfect matching edge, then the third vertex must be an endpoint of a perfect matching edge that is a bridge, and therefore, by Lemma <ref>, we are done. Thus, we may assume that the three perfect matching edges incident with the 3-cycle are distinct.  For the same reason, we may assume that all three perfect matching edges are all outside of the 3-cycle or are all inside the 3-cycle.  Thus, we may assume, without loss of generality,  that the 3-cycle, with distinct perfect matching edges at each vertex, appears as in Figure <ref>.



Because the polynomial is calculated recursively, the cube of resolutions for ⟨G:M⟩_2(1) may be decomposed as follows.  First, resolve every perfect matching edge that is not incident to the 3-cycle to get 2^k-3 “prestates."  Each prestate P will consist of a number of immersed circles and a graph G' whose vertices are spanned only by the three perfect matching edges of the 3-cycle.  Note: the graph G' may be immersed away from the 3-cycle and the three perfect matching edges.  If there are ℓ immersed circles in the prestate P, then by the relations in Figure <ref>, 
    ⟨ P ⟩_2(1) =  2^ℓ·(⟨ G' ⟩_2(1)).

We will show that in all possible cases for G', ⟨ G' ⟩_2(1) = 0.  Since ⟨G:M⟩_2(1) is made up as sums of terms of the form ±⟨ P ⟩_2(1), and each of these terms is zero,  ⟨G:M⟩_2(1)=0.

Resolving all three perfect matching edges of the 3-cycle using all open-resolutions )( produces the picture shown in Figure <ref>. Thus, the “all-open-resolution” of the graph G' of a prestate P  corresponds to a choice of connecting the six endpoints of Figure <ref> with three arcs.  



Up to symmetry of the disk, there are seven ways to connect these six endpoints up to form a set of immersed circles.  These seven configurations are shown in Figure <ref>. (The actual all-open-resolution of a particular G' may have more circle intersections, of course, but these extra intersections do not effect any of the calculations.)  Thus, to prove ⟨ G'⟩_2(1)=0 for all possible graphs G' of the prestates, we need only show that it is zero for these seven configurations.



The cube of resolutions corresponding to the first all-open-resolution configuration in Figure <ref> is shown in Figure <ref>.  For a G' corresponding to this configuration, we see that ⟨ G' ⟩_2(1)= 2-3· 2+3· 2-2=0.  The remaining six cases are handled in the Appendix. In each case, ⟨ G'⟩_2(1)=0, which proves the lemma.








§ PROOF OF THEOREM <REF>


Now we are ready to prove Thoerem <ref>. Because both ⟨ G:M⟩_2(z) and |G:M|_2 are multiplicative under disjoint unions, we need only prove Theorem <ref> for the case when G is a connected graph.  Furthermore, by Lemma <ref>, the theorem is trivially true if G has a bridge.  Therefore we need only prove the theorem for connected, bridgeless planar trivalent graphs.


The proof proceeds by induction on the number of edges in the perfect matching M.  If the perfect matching has a single edge, then (G,M) is the θ graph, and the theorem is  verified by inspection.  

Assume the theorem is true for  any planar trivalent graph with a perfect matching having n-1 edges.  Let (G,M) be a connected, bridgeless planar trivalent graph with n perfect matching edges.  By Lemma <ref>, the graph is IH-equivalent to (G',M'), where G'(V',E'∖ M') has a cycle of length at most 3.  Lemma <ref>, together with the inductive hypothesis, implies that we need only verify that the result holds for (G', M'). 

If G'(V',E'∖ M') has a cycle of length 3, then Proposition <ref>  and Lemma <ref> imply the result.  If G'(V',E'∖ M') has a cycle of length 1, then G' has a bridge and Lemma <ref> implies the result.  Lastly, if G'(V',E'∖ M') has no cycle of length 1 or 3, but does have a cycle of length 2, then Lemma <ref> (the Bubble Lemma), together with the inductive hypothesis, implies the result.  





§ CONCLUDING REMARKS


In working with the 2-factor polynomial, the authors noticed a close relationship between planar trivalent graphs with perfect matchings and virtual links, which will be explored in <cit.>. While Theorem <ref> was first proved in this paper, in the context of planar trivalent graphs, this relationship suggested that an equivalent result might hold for the Jones polynomial of a virtual link.  In a later paper (cf. Theorem 5 of <cit.>), we prove the corresponding theorem in virtual link theory.

The graph-theoretic proof presented in this paper is distinctly different than the knot-theoretic proof of <cit.>.  We feel this proof has value from a graph theory perspective.  At the heart of our argument, we are essentially inducting on the number cycles in G∖ M, which reduces the problem to studying the base-case of a Hamiltonian graph, i.e., a graph G' and perfect matching M' with the same number of vertices and edges as (G,M) but with a single cycle for G'∖ M'. We believe that this technique will be of value and interest to graph theorists when proving theorems like this one.

Finally, this paper, together with <cit.>, <cit.>, and <cit.>, establishes a relationship between the categorification of the 2-factor polynomial and virtual Khovanov homology. Other fruitful relationships between graph and knot polynomials and their categorifications are well-known (cf. <cit.>). In each of these relationships, the graph theoretic and knot theoretic viewpoints mutually inform and reinforce one another. We see this connection between the categorification of the 2-factor polynomial and virtual Khovanov homology as a promising avenue for future research.

99

AppelHaken K. Appel and W. Haken, Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics, 21, pp. 429–490, 1977.

AppelHaken2 K. Appel, W. Haken, J. Koch, Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics, 21, pp. 491–567, 1977.

BaldCohomology S. Baldridge,  A Cohomology Theory for Planar Trivalent Graphs with Perfect Matchings.  	arXiv:1810.07302.

BaldKauffMc S. Baldridge, L.H. Kauffman, B. McCarty, Unoriented Virtual Khovanov Homology.  arXiv:2001.04512.

BKR S. Baldridge, L. H. Kauffman, W. Rushworth.  On ribbon graphs and virtual links. In Preparation.

BN2 D. Bar Natan, Lie algebras and the four color theorem, Combinatorica 17 (1997), no. 1,  43-52.

DFKLS O.T. Dasbach, D. Futer, E. Kalfagianni, X.S. Lin, N. Stoltzfus, The Jones polynomial and graphs on surfaces, J. Combin. Theory Ser. B, 98 (2008), no. 2, 384-399.

DL O.T. Dasbach, A.M. Lowrance, A Turaev surface approach to Khovanov homology, Quantum Topol. 5 (2014), no. 4, 425-486.

Heawood P. J. Heawood, Map-colour theorem, Quarterly Journal of Mathematics 24 (1890), 332-338.

Kauffman3 L. H. Kauffman, Map coloring and the vector cross product, J. Combin. Theory Ser. B 48 (1990), 145-154.

KauffmanStateCalc L. H. Kauffman, A state calculus for graph coloring, Illinois J. Math. 60 (2016), no. 1, 251-271.



KauffmanTutte L. H. Kauffman, A Tutte polynomial for signed graphs, Discrete Appl. Math. 25 (1989), no. 1-2, 105-127. 

Kempe A. B. Kempe, On the Geographical Problem of the Four Colours, American Journal of Mathematics, The Johns
Hopkins University Press 2 (1879), no. 3, 193-220.


LM M. Loebl, I. Moffatt, The chromatic polynomial of fatgraphs and its categorification, Adv. Math. 217 (2008), no. 4, 1558-1587.

RSST N. Robertson, D. P. Sanders, P. Seymour, R. Thomas, The four-colour theorem, J. Combin. Theory
Ser. B 70 (1997), 2-44.

Thistlethwaite M. Thistlethwaite, A spanning tree expansion of the Jones polynomial, Topology 26 (1987), no. 3, 297-309.





§ APPENDIX

The remaining cases for Lemma <ref> are presented here.





















