2025/10/11 by Kalimullin, Ilyas, Lerner, Eduard
#05C15 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2510.10213
Consider a connected pseudograph H such that each edge is associated with weight xe, xe ∈ \mathbbF3; T(H) is the set of spanning trees of graph H. Assume that s(H;\mathbf x)=∑T\inT(H) ∏e∈ E(T) xe. Let G be a maximal planar graph (arbitrary planar triangulation) such that each face F is assigned the value α(F)=± 1 ∈ \mathbbF3. Then we can associate each edge with xe=α(F'e)+α(F''e), where F'e and F''e are the faces containing edge e. Let us define the value wG(\mathbf x) as (\fracs(G/W^*(\mathbf x);\mathbf x)3)/(-3)^(|V(G/W^*(\mathbf x))| - 1)/2; here (\fracx3) is the Legendre symbol, G/W is the graph with the contracted set of vertices W, while W^*(\mathbf x) is a set of vertices W, W ⊆ V(G), with minimal cardinality such that s(G/W;\mathbf x) differs from zero. In the following, we prove that the number of Tait colorings for graph G equals the tripled sum wG(\mathbf x(α)) with respect to all possible vectors α∈ \-1, 1\\mathcal F(G) such that G/W^*(\mathbf x(α)) has an odd number of vertices, where \mathcal F(G) is the set of faces of graph G. Keywords: maximal planar graph, Tait coloring, Laplace-Kirchhoff matrix, spanning tree.