Now suppose $0 < t < r$. In particular, we know that $m_1 > 1$, which means the valence at $v_\opt$ will not change when we pass from $\mathcal{G}_v$ to $\mathcal{G}_S$. However, the valence of the vertex $v_\fix$ will decrease from $(r-1) \oplus 0$ to $(t-1) \oplus 0$ because we will remove the diagonals $I_i^1$ for all $t+1 \leq i \leq r$. For each such $i$, the only remaining edge with a label of the form $I_j^i$ will be the edge incident to $v_\opt$ with label $I_1^i$, and the only other edge the  vertices $N_{\Gamma'}(I_j^i) \backslash \{v\}$ are incident to is $Y_{I_v}$. Therefore, this edge now behaves just as the edges $(v,a_i)$ for $a_i >_{\mathcal{I}} v$. In Lemma <ref>, we see that if $r = 1$ or $r = 2$, exactly one admissible matching uses the edge weighted $Y_{I_v}$. Now, suppose $r > 2$ and let $\mathcal{H}_2,\ldots,\mathcal{H}_r$ be the branch snake graphs from $\mathcal{G}_v$. The edge $Y_{I_v}$ is in each branch snake graph and by definition the distinguished non-matching does not include $Y_{I_v}$. Therefore, by Lemma <ref>, any matching including this edge is in $\mathcal{P}_v^1$. In the proof of Theorem <ref> for $r > 2$, we analyze the weights of matchings in $\mathcal{P}_v^1$ and we again see that there is only one admissible matching including $Y_{I_v}$. Therefore, all other matchings must include the edge $Y_{I_j^i}$, which matches what we expect from Proposition <ref>.

§.§ General Proof

We turn to proving Theorem <ref> for sets with larger rooted portions with the following steps.  First, in Lemma <ref> we show an identity  involving $Y_S, Y_T,$ and $Y_{S \cup T}$ for disjoint incompatible sets $S$ and $T$ on a tree. Our goal is then to show, for a weakly rooted set $S \cup J_{\mathbf{m}}$ with $S$ weakly rooted, and $S$ and $J_{\mathbf{m}}$ disjoint, the same relation holds for $\chi(S), \chi(J_{\mathbf{m}}),$ and $\chi(S\cup J_{\mathbf{m}})$.  In Lemma <ref> we show that the admissible matchings of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ can always be decomposed to admissible matchings of $\mathcal{G}_{S}$ and $\mathcal{G}_{J_{\mathbf{m}}}$ such that at least one of these matchings used the glued edge. Then, in Lemma <ref>, we study the set of matchings of a snake graph $\mathcal{G}_{S}$ which do not use a given boundary edge. These two results put together show that the sums of admissible matchings satisfies the same relation as for $Y$-variables in Lemma <ref>. The proof of Theorem <ref> follows quickly from these results.

Let $\Gamma$ be a tree. Let $S,T \subset V(\Gamma)$ be disjoint, connected sets of vertices and suppose there exists $(w,v) \in E(\Gamma)$ such that $w \in S,  v \in T$.  Then, $Y_{S}Y_{T} = Y_{S\cup T} + Y_{S \backslash \{w\}}Y_{T \backslash \{v\}}$.

Note that the sets $S \backslash \{w\}, T \backslash \{v\}, S, $ and $S \cup T$ with the given conditions are all compatible.  Suppose $\mathcal{I}$ is a cluster containing these sets; it is possible that $S \backslash \{w\}$ or $T \backslash \{v\}$ is disconnected, in which case $\mathcal{I}$ would contain all connected components. In this cluster, the mutation of the set $S$ produces the set $T$, and the expansion of $Y_{S}Y_{T}$ follows from Equation (5.2) of <cit.>.

To prepare for further arguments involving admissible matchings, we show that Proposition <ref> will also hold for general weakly rooted sets.

Let $S$ be a weakly rooted set and let $P$ be an admissible matching of $\mathcal{G}_S$. Let $e_1$ and $e_2$ be two internal edges which both share vertices with diagonals $d_1$ and $d_2$. Then, $e_1$ and $e_2$ are either both in $P$ or neither are in $P$.

We construct $\mathcal{G}_S$ by gluing snake graphs of the form $\mathcal{G}_{J_{\mathbf{m}}}$. This process takes an edge of the form $(v,w)$ in two such snake graphs and glues them together to form a new internal edge. There will be no other internal edge which shares vertices with the same set of diagonals as this glued edge. Therefore, any pair of distinct internal edges as in the statement must have come from one of the snake graphs $\mathcal{G}_{J_{\mathbf{m}}}$. One can then use the same proof strategy as in Lemma <ref> to show the result.

Given a weakly rooted set $S$,  let $\mathcal{P}_S$ be the set of admissible matchings of $\mathcal{G}_{S}$.  Given an edge $e$ in a snake graph $\mathcal{G}_S$, let $\mathcal{P}_S^e$ denote the set of admissible matchings of $\mathcal{G}_S$ that contain $e$, and  let $\mathcal{P}_S^{ne}:= \mathcal{P}\backslash \mathcal{P}_S^e$ denote the complement.
For example, we could rephrase Corollary <ref> as saying that, given a dominant boundary edge $e$ in $\mathcal{G}_v$, there is a unique matching in $\mathcal{P}_v^{ne}$.

Consider disjoint, weakly rooted sets $S$ and $J_{\mathbf{m}}(v) = J_{\mathbf{m}}$ such that there exists $w \in \overline{S}$ with $(v,w) \in E(\Gamma)$ and $w >_{\mathcal{I}} v$.

* There does not exist an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ which contains all edges incident to $v$ which come from $\mathcal{G}_S$.

* There does not exist an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ which contains only edges from $\mathcal{G}_S$ incident to $v$ and only edges from $\mathcal{G}_{J_{\mathbf{m}}}$ incident to $w$.

* There does not exist an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ which does not include any edges incident to $v$ which come from $\mathcal{G}_S$ and includes all edges incident to $w$ but not $v$ which come from $\mathcal{G}_S$.

The three statements above are also true if we switch $v$ and $w$ and/or if we switch $\mathcal{G}_S$ and $\mathcal{G}_{J_{\mathbf{m}}}$ in each statement.  (Note that this means (1) and (3) each give four statements and (2) gives two statements.)

There are three cases for the local configuration near the edge $(v,w)$ in $\mathcal{G}_{S \cup J_{\mathbf{m}}}$, based on whether $w$ covers $v$ or not, and if it does, whether the diagonal $I_v$ in the graph $\mathcal{G}_{S}$ is incident to a vertex $w_\opt$ or $w_\fix$.  Since we will frequently be referring to the set $N_\Gamma(v) \cap \Gamma^{\mathcal{I}}_{<v}$ in the following text and figures, we will introduce the shorthand $\mathcal{N}_v:= N_\Gamma(v) \cap \Gamma^{\mathcal{I}}_{<v}$.

Case 1: First, suppose $v \lessdot w$ and the diagonal $I_v$ in $\mathcal{G}_S$ is incident to $w_\opt$ so that $a_1(w) = v$. This means that we glue on the edge $(v_\opt,w)$ in $\mathcal{G}_{J_{\mathbf{m}}}$ and on the edge $(v,w_\opt)$ in $\mathcal{G}_S$. The local configuration is shown below.   Note that some of the edges adjacent to $v_{\text{opt}}$ from $\mathcal{G}_{J_{\mathbf{m}}}$ could share vertices with the edge $Y_{I_v}$; we draw our diagram simply to focus on which edges are adjacent to $v_{\text{opt}}$ and $w_{\text{opt}}$. Note also that there could be edges of the form $(v_{\text{opt}},u)$ or $(w_{\text{opt}},u)$ for  for $u>_{\mathcal{I}} v$ and $u>_{\mathcal{I}} w$ respectively which have weight 1.  Since in $\mathcal{G}_{S}$, the valence of $w_{\text{opt}}$ is $(1 \oplus \deg_{\Gamma'}(w)-2)$ and the valence of $v$ is $(1 \oplus \deg_{\Gamma'}(v) - 2)$ and in $\mathcal{G}_{J_{\mathbf{m}}}$, the valence of the vertex $w$ is $(1 \oplus 0)$ and the valence of $v_{\text{opt}}$ is $(1 \oplus \deg_{\Gamma'}(v) - 2)$, in the glued graphs these vertices have valences $(1 \oplus \deg_{\Gamma'}(w)-2)$ and $(1 \oplus 2\deg_{\Gamma'}(v) -4)$ respectively.

[scale = 1.2]
[white] at (5,-1)$(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$;
(v) at (0,0) $v_{\text{opt}}$;
(w) at (2,0) $w_{\text{opt}}$;
(v) – (w);
(v) – (-.3,1.5);
(v) – (0,1.5);
(v) – (.3,1.5);
[] at (-1.5,1)$\cup_{a_i(v) \in \mathcal{N}_v} Y_{I_1^i(v)}$;
(w) – (1.7,1.5);
(w) – (2,1.5);
(w) – (2.3,1.5);
[] at (4,1)$(\cup_{a_i(w) \in \mathcal{N}_w \backslash \{v\}} Y_{I_1^i(w)})$;
(w) – (2,-1);
(2,-1) – (2.3,-1.5);
(2,-1) – (2,-1.5);
(2,-1) –  (1.7,-1.5);
[] at (2.6,-1)$Y_{I_v}$;
(v) – (-.3,-1.5);
(v) – (0,-1.5);
(v) – (0.3,-1.5);
[] at (-3,-1)$(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$;
[dashed] (v) to node[right, yshift = 5pt, xshift = -5pt]$I_1^1(v)$ (1.7,-1.5);
[dashed] (w) to node[right]$I_v$ (0.4,1.3);
(-.3,1.7) – (0,2) to node[above]$Y_{I_w}$ (2,2) – (2.3,1.7);
(0,1.7) – (0,2) – (.3,1.7);
(2,1.7) – (2,2) – (1.7,1.7);

First, we will show statement (1) holds for this case.  If $P$ contains $(v,w)$, it cannot contain the edge $Y_{I_v}$ by Condition (<ref>) from Definition <ref> so we see immediately it cannot contain all edges coming from $\mathcal{G}_{J_{\mathbf{m}}}$ which are incident to $w$. Since the valence of $w$ in $\mathcal{G}_{J_{\mathbf{m}}}$ is $1 \oplus 0$, the valence of $w$ in $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ is the same as in $\mathcal{G}_S$. This valence does not allow an admissible matching to include every edge incident to $w_{\opt}$ from $\mathcal{G}_{J_{\mathbf{m}}}$, so we do not need to consider such a configuration in $\mathcal{G}_{S\cup J_{\mathbf{m}}}$ either.

Now, assume that $P$ contains all edges incident to $v$ which come from $\mathcal{G}_S$. Since this includes the edge $(v,w)$, we cannot include the edge weighted $Y_{I_w}$ by Condition (<ref>) of Definition <ref>. This means the edges $(w_{\opt},u)$ for any $u \in N_{\Gamma'}(w) \cap (\Gamma')^{\mathcal{I}}_{>w}$ must  be in $P$ since these vertices are only incident to the edge $(w_{\opt},u)$ and the edge weighted $Y_{I_w}$.
Therefore, there is some $a_i(w) \in \mathcal{N}_w$ such that the edge $Y_{I_1^i(w)}$ incident to $w_\opt$ is not in $P$.  Then,  we claim there is no way to find an edge which is incident to the vertices $N_\Gamma(I_1^i(w)) \backslash \{w\}$ and which  can be included to such a set of edges and preserve admissibility. We draw the general situation below, where  the set of vertices which attain the contradiction are marked with *.

[scale = 2]
(5) at (2,1);
(6) at (2,0);
(3) at (0,1)$w$;
(4) at (1,1);
(1) at (0,0);
(2) at (1,0)*;
(v) at (0,-1)$v$;
(w) at (1,-1)$w_\opt$;
(3) to node[above]$Y_{I_2^i(w)}$ (4);
(3) to node[left]$Y_{I_v}$ (1);
(4) – (2);
(1) – (v);
(1) to node[above]$Y_{I_w}$ (2);
(v) – (w);
(2) to node[right]$Y_{I_1^i(w)}$(w);
(2) to node[below]$Y_{I_1^i(w)}$ (6);
(6) – (5);
(5) – (4);
[dashed] (1) to node[right]$I_v$ (w);
[dashed] (3) to node[right, yshift = 8pt, xshift = -8pt]$I_1^i(w)$ (2);
[dashed] (4) to node[right, yshift = 8pt, xshift = -8pt]$I_2^i(w)$ (6);

Note that the edge $Y_{I_2^i(w)}$ must be included in $P$ since by valence requirements of the vertices in the set $N_{\Gamma'}(I_v) \backslash \{v\}$ and the assumption that we are including all edges incident to $v$, we cannot include the edge $Y_{I_v}$.  Thus,  by valence requirements and Condition (<ref>) of Definition <ref>, none of the edges incident to * can be included in $P$. If $c_i = 1$, then the picture is simpler and the claim follows by similar logic.

Finally, we consider the situation where $P$ contains all edges incident to $v$ which comes from $\mathcal{G}_{J_{\mathbf{m}}}$. First, suppose $r > 2$, so that $\mathcal{G}_{J_{\mathbf{m}}}$ has a vertex $v_\fix$ with valence $(r - 1) \oplus 0$. From the proof of Lemma <ref>, we see that if $J_{\mathbf{m}} = \{v\}$, the subset of $P$ consisting of edges incident to $v_\fix$ puts restrictions on which edges incident to $v_\opt$ can be in $P$, and the same arguments hold for a more general set $J_{\mathbf{m}}$. In order for such a configuration to satisfy the admissibilty criteria, $P$ must also include the edges with weights $Y_{I_{1}^2(v)},\ldots,Y_{I_{1}^r(v)}$ incident to $v_\fix$. However, we can reach a similar contradiction to the previous discussion now and show that we cannot add any edges incident to $N_{\Gamma'}(I_1^1(v))$ to this matching and preserve admissibility.
When $r \leq 2$ or $\{v\} \subsetneq J_{\mathbf{m}}(v)$, we can quickly reach the same contradiction without appealing to any previous result.

We will now  prove statement (2) in this case.  If  the set of edges in $P$ incident to $v$ lie only in $\mathcal{G}_S$ and the set of edges in $P$ incident to $w$ lie only in $\mathcal{G}_{J_{\mathbf{m}}}$, $P$ could not be decomposed into admissible matchings of $\mathcal{G}_S$ and $\mathcal{G}_{J_{\mathbf{m}}}$ since, even if we add the edge $(v,w)$ to one of the decompositions, the other decomposition would leave either $v$ or $w$ uncovered, which would not respect the valences in $\mathcal{G}_S$ and $\mathcal{G}_{J_{\mathbf{m}}}$.
By Condition (<ref>) in Definition <ref>, we cannot use the edge labeled $I_1^1(v)$ incident to $v$ and the edge $Y_{I_v}$ incident to $w$. If we use the edge $Y_{I_v}$ incident to $w$ and a proper subset of the edges incident to $v$ lying in $\mathcal{G}_S$, then we cannot use the edge labeled $I_w$ since the endpoints of the edges incident to $v$ in $P$ will have valence $1 \oplus 0$. This would leave the vertices in $N_\Gamma(I_1^1(v))\backslash \{v\}$ without any incident edge in the matching.
Therefore, there cannot be an admissible matching with the edges incident to $v$ lying only in $\mathcal{G}_S$ and the edges incident to $w$ lying only in $\mathcal{G}_{J_{\mathbf{m}}}$.

Now, suppose that we have an admissible matching such that the set of edges in $P$ incident to $v$ lie only in $\mathcal{G}_{J_{\mathbf{m}}}$ and the set of edges in $P$ incident to $w$ lie only in $\mathcal{G}_S$. Then, we again cannot include the edge $Y_{I_w}$ due since the endpoints of some of the endpoints of the edge are already covered. Moreover, by assumption we do not include the edge $Y_{I_1^1(v)}$,  so we cannot complete such a configuration to include any edges which cover $N_\Gamma(I_1^1(v)) \backslash \{v\}$.

Finally, we turn to proving statement (3). First, we show that there does not exist an admissible matching of $\mathcal{G}_{S \cup \Jm}$ that does not include any edges incident to $v$ from $\mathcal{G}_{\Jm}$ but includes all edges from $\mathcal{G}_{\Jm}$ which are incident to $w$ but not to $v$. If we have $Y_{I_v} \in P$,  by Condition (<ref>) we cannot have $Y_{I_1^1(v)}$ as well.  However, we must include some of the incident to $v$ which only lie in $\mathcal{G}_{S}$. By Condition (<ref>) if we include some of these, we must include all of them, forcing us to include $Y_{I_1^1(v)}$.

Now we will show there does not exist an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ which does not include any edges incident to $v$ which come from $\mathcal{G}_S$ and includes all edges incident to $w$ but not $v$ which come from $\mathcal{G}_S$. If we include all edges incident to $w$ which lie only in $\mathcal{G}_S$, we cannot include $Y_{I_w}$ since all vertices incident to this edge have valence $1 \oplus 0$ and now some are already covered. If $\vert \mathcal{N}_w \vert = 1$, then since we assumed we did not include any edges incident to $v$ which lie only in $\mathcal{G}_S$, there are no other edges incident to the vertices $N_{\Gamma'}(I_v) \backslash \{w\}$,  so we cannot complete this to an admissible matching. If $\vert \mathcal{N}_w \vert > 1$,  then there will be an edge $Y_{I_v}$ incident to these vertices,  but we cannot include it by Condition (<ref>).

Lastly, the last two statements from (3) follow from the same argument that we used to show we cannot have an admissible matching of $\mathcal{G}_{S \cup \Jm}$ which includes all edges incident to $v$ which come from $\mathcal{G}_{\Jm}$ or which includes all edges incident to $v$ which come from $\mathcal{G}_S$.

Case 2: Now, suppose $v \lessdot w$ and the diagonal $I_v$ in $\mathcal{G}_S$ is incident to $w_\fix$. The local configuration is again drawn below; note that $w_{fix}$ is adjacent to $m-1$ more diagonals for some $m \leq \vert \mathcal{C}_w \vert$ determined by which parts of $\mathcal{G}_w$ are removed in $\mathcal{G}_w^S$.  In $\mathcal{G}_S$, the valence of $w_\fix$ is $m \oplus 0$ and the valence of $v$ is $(1 \oplus \deg_{\Gamma'}(v)  - 2)$. The valences in $\mathcal{G}_{J_{\mathbf{m}}}$ are the same as in case 1. Therefore, in $\mathcal{G}_{S \cup J_{\mathbf{m}}}$, the valence of $w$ is $(m \oplus 0)$ and the valence of $v$ is $(1 \oplus 2\deg_{\Gamma'}(v) -4)$.

(v) at (0,0) $v_{\text{opt}}$;
(w) at (2,0) $w_{\text{fix}}$;
(v) – (w) ;
(v) – (-.3,1.5);
(v) – (0,1.5);
(v) – (.3,1.5);
[] at (-1.5,1)$\cup_{a_i(v) \in \mathcal{N}_v} Y_{I_1^i(v)}$;
(w) – (1.7,1.5);
(w) – (2,1.5);
(w) – (2.3,1.5);
[] at (5.2,1)$(\cup_{a_i(w) \in \mathcal{N}_w \backslash \{a_1(w)\}} Y_{I^{i}_2(w)}) \cup Y_{I_1^{1}(w)}$;
(w) – (2,-1);
(2,-1) – (2.3,-1.5);
(2,-1) – (2,-1.5);
(2,-1) –  (1.7,-1.5);
[] at (2.6,-1)$Y_{I_v}$;
(v) – (-.3,-1.5);
(v) – (0,-1.5);
(v) – (0.3,-1.5);
[] at (-3,-1)$(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$;
[dashed] (v) to node[right, xshift = -5pt, yshift = 5pt]$I_1^1(v)$ (1.7,-1.5);
[dashed] (0.4,1.4) to node[right]$I_v$ (w);

We will now prove statement (1) for this case. We can immediately rule out encountering an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ which includes all edges incident to $w$ coming from $\mathcal{G}_S$ or $\mathcal{G}_{J_{\mathbf{m}}}$ by valence considerations and Condition (<ref>) of Definition <ref> respectively.

Suppose for sake of contradiction that there exists an admissible matching $P$ of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ containing all edges incident to $v$ which come from $\mathcal{G}_S$.  Since $P$ includes $(v_{opt},w)$, by Condition (<ref>) of admissibility the edge $Y_{I_v}$ cannot be in $P$, so $P$ must contain all other edges $(v_\opt,u)$ for $u \in N_{\Gamma'}(v) \cap \Gamma^{\mathcal{I}}_{>v}$ which come from $\mathcal{G}_{J_{\mathbf{m}}}$. The only edges we do not need to include are  edges from the set $(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$ which has size $r = \vert \mathcal{N}_v \vert$. If $r= 1$, then we have included $2\deg_{\Gamma'}(v) - 2$ edges incident to $v$, which violates the valence of $v$ in $\mathcal{G}_{S \cup J_{\mathbf{m}}}$.

Now, assume $r > 1$.  Then there are at least two edges from the set of edges with weights $(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$  from $\mathcal{G}_{J_{\mathbf{m}}}$ which cannot be in $P$.  At least one of these edges must have a label $I_1^i(w)$ for $a_i(w) \in \mathcal{N}_v, a_i(w) \neq a_1(w)$.  We first claim this means we cannot use the edge $Y_{I_1^1(v)}$ incident to $v_\fix$.

The situation is drawn below. Suppose we do include this edge. Then,  $P$ must also include the edge $Y_{I_2^i(v)}$ incident to diagonal $I_1^i(v)$ since the vertices in the set $N_{\Gamma'}(I_1^1(v)) \backslash \{v\}$ have valence $1 \oplus 0$.  If $r > 2$, then by similar logic as in the proof of Lemma <ref>,  we will see that there is no way to complete this to an admissible matching and contain at least one edge incident to the vertices denoted * below. If $r = 2$, then we can use a simpler version of the logic from this proof.

(vopt) at (0,0)$v$;
(b12) at (1,0)*;
(b22) at (2,0);
(v) at (1,1)$v_\opt$;
(vfix) at (2,-1)$v$;
(b11) at (1,-1);
(vreallyfix) at (3,0)$v_\fix$;
(vopt) to node[above]$Y_{I_1^i(v)}$ (b12);
(b12) to node[above]$Y_{I_v}$ (b22);
(b12) to node[left]$Y_{I_1^i(v)}$ (v);
(b12) to (b11);
(vfix) to node[right]$Y_{I_1^i(v)}$ (b22);
[dashed] (v) to node[right, xshift = -5pt, yshift = 5pt]$I_1^1(v)$ (b22);
[dashed] (b12) to node[right, xshift = -5pt, yshift = 5pt]$I_1^i(v)$ (vfix);
(vfix) to node[below]$Y_{I_2^i(v)}$ (b11);
[dashed] (vopt) to node[right, xshift = -5pt, yshift = 5pt]$I_2^i(v)$(b11);
(b22) to node[above]$Y_{I_1^1(v)}$ (vreallyfix);

Therefore,  $P$ must include all other edges incident to $v_\fix$.  In particular,  $P$ includes $I_2^i(v)$ for the designated $a_i(v) \in \mathcal{N}_v$ where $P$ does not include the edge $Y_{I_1^i(v)}$ incident to $v_\opt$. We claim that there is no way to complete this to an admissible matching such that there is at least one edge incident to any vertex in the set $N_\Gamma(I_1^i(v)) \backslash \{v\}$, in the position denoted by * below.  By assumption,  we do not include the edge $Y_{I_1^i(v)}$ incident to $v_\opt$, and the other edge labeled $Y_{I_1^i(v)}$ cannot be included by Condition (<ref>) of Definition <ref>  since we include the edge $Y_{I_2^i(v)}$ incident to $v_\fix$.  We already showed we do not include $Y_{I_v}$.  We can show that the remaining set of internal edges cannot be included by an argument akin to those in the proofs of Lemma <ref> and <ref>.

[scale = 2]
(vopt) at (0,0)$v_\opt$;
(1) at (0,-1);
(2) at (1,-1);
(star) at (1,0)*;
(vfix) at (2,-1)$v_\fix$;
(3) at (2,0);
(4)at (1,1);
(5) at (2,1);
(vopt) – (1);
(vopt) to node[above]$Y_{I_1^i(v)}$ (star);
(2) to node[right]$Y_{I_v}$ (star);
(2) to node[below]$Y_{I_1^1(v)}$ (vfix);
(vfix) to node[right]$Y_{I_2^i(v)}$ (3);
(3) – (5);
(star) to node[left]$Y_{I_1^i(v)}$ (4);
(star) – (3);
[dashed] (vopt) to node[right, xshift = -5pt, yshift = 5pt]$I_1^1(v)$ (2);
[dashed] (star) to node[right, xshift = -5pt, yshift = 5pt]$I_1^i(v)$ (vfix);
[dashed] (4) to node[right, xshift = -5pt, yshift = 5pt]$I_2^i(v)$ (3);

By the same logic as in case 1,  there cannot be an admissible matching of $\mathcal{G}_{S\cup J_{\mathbf{m}}}$ containing all edges incident to $v$ which come from $\mathcal{G}_{J_{\mathbf{m}}}$.  This finishes the proof of statement (1) for this case.

Statement (2) is true in this case by the same logic as in case 1. Statement (3) is true for cases ($v,\mathcal{G}_{\Jm}$), ($v,\mathcal{G}_{S}$), and ($w,\mathcal{G}_{\Jm}$) for the same logic as in case 1 as well; the case ($w,\mathcal{G}_{S}$) is impossible for some graphs $\mathcal{G}_{S \cup \Jm}$ as it is possible that $w = w_{\fix}$ has valence $r \oplus 0$ for $r > 1$. If this is not the case, then we again can use similar logic.

Case 3: Finally, suppose $v < w$ but $w$ does not cover $v$.  Then there is a unique vertex $u$ of $\Gamma$ such that $v \lessdot u$. The valence of $v_{\text{opt}}$ in the glued graph is again $(1 \oplus 2\deg_{\Gamma'}(v) - 4)$ and the valence of the vertex $w$ on the glued edge is $(1 \oplus 0)$.

[scale = 1.5]
[white] at (4,-1)$(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$;
[] at (0,0) $v_{\text{opt}}$;
[] at (2,0) $w$;
(.2,0) – (1.8,0);
(0,.2) – (-.3,1.5);
(0,.2) – (0,1.5);
(0,.2) – (.3,1.5);
[] at (-1.1,1)$\cup_{a_i(v) \in \mathcal{N}_v} Y_{I_1^i(v)}$;
(2,.2) – (2,1);
(2,1) – (1.7,1.5);
(2,1) – (2,1.5);
(2,1) – (2.3,1.5);
[] at (2.6,1)$Y_{I_{u}}$;
[dashed] (1.8,0.2) to node[right]$I_v$ (.3,1.5);
(2,-.2) – (2,-1);
(2,-1) – (2.3,-1.5);
(2,-1) – (2,-1.5);
(2,-1) –  (1.7,-1.5);
[] at (2.6,-1)$Y_{I_v}$;
(0,-.2) – (-.3,-1.5);
(0,-.2) – (0,-1.5);
(0,-.2) – (0.3,-1.5);
[] at (-2,-1)$(\cup_{a_i(v) \in \mathcal{N}_v \backslash \{a_1(v)\}} Y_{I_1^i(v)}) \cup Y_{I_2^1(v)}$;
[dashed] (0.2,-0.2) to node[right, xshift = -5pt, yshift = 5pt]$Y_{I_1^i(v)}$ (1.7,-1.5);

To prove statement (1), since the vertex $w$ has valence $1 \oplus 0$, we do not need to consider a matching using all edges incident to $w$ in $\mathcal{G}_S$.  Similarly, we do not need to consider a matching using all edges incident to $w$ in $\mathcal{G}_{J_{\mathbf{m}}}$.

If $P$ includes the edge $(v_\opt,w)$ as well as an edge from $\mathcal{G}_S$ with a weight from the set $\cup_{a_i(v) \in \mathcal{N}_v} Y_{I_1^i(v)}$,  Condition (<ref>) of Definition <ref> would force us to include the edge $Y_{I_u}$ incident to $w$. This violates the valence of $w$, so we cannot have a matching which uses every edge incident to $v$ from $\mathcal{G}_S$. Showing that we will not have an admissible matching which uses all edges incident to $v$ coming from $\mathcal{G}_{J_{\mathbf{m}}}$ follows the same logic as in the previous cases as it only relies on properties of $\mathcal{G}_{J_{\mathbf{m}}}$.

Now we turn to  statement (2) and consider matchings such that the edges incident to $v$ come from one snake graph and the edges incident to $w$ come from the other snake graph. If we include the edge $Y_{I_u}$ incident to $w$ in an admissible  matching, by Condition (<ref>) of Definition <ref> we must use all the edges from $\mathcal{G}_S$ labeled $I_1^i(v)$ and similarly if we include at least one such edge,  we must include the edge $Y_{I_u}$. Therefore,  it is impossible for there to be an admissible matching of $\mathcal{G}_{S \cup J_{\mathbf{m}}}$ such that the edges incident to $v$ only lie in $\mathcal{G}_S$ and the edges incident to $w$ only lie in $\mathcal{G}_{J_{\mathbf{m}}}$ or vice versa.

We can quickly show statement (3)  by combining admissibility Conditions (<ref>) and (<ref>) which imply that we have $Y_{I_u}$ in an admissible matching if and only if we have all edges which lie only in $\mathcal{G}_S$ and which are incident to $v$.

Consider disjoint, weakly rooted sets $S$ and $J_{\mathbf{m}}(v) = J_{\mathbf{m}}$ such that there exists $w \in \overline{S}$ with $(v,w) \in E(\Gamma)$ and $w >_{\mathcal{I}} v$.
For any pair of matchings $(P_S,P_{J_{\mathbf{m}}}) \in \mathcal{P}_S \times \mathcal{P}_{J_{\mathbf{m}}}$ such that the edge $(v,w)$ is included in $P_S$ or $P_{J_{\mathbf{m}}}$, there is a matching $P \in \mathcal{P}_{S \cup J_{\mathbf{m}}}$ formed by taking the union of $P_S$ and $P_{J_{\mathbf{m}}}$ and deleting an instance of $(v,w)$.
Moreover, any admissible matching $P \in \mathcal{P}_{S \cup J_{\mathbf{m}}}$ has restrictions $P\vert_{\mathcal{G}_{S}}$ and $P\vert_{\mathcal{G}_{J_{\mathbf{m}}}}$ that are admissible matchings of $\mathcal{G}_{S}$ and $\mathcal{G}_{J_{\mathbf{m}}}$ respectively when $(v,w)\in P$, and can be completed to admissible matchings of $\mathcal{G}_{S}$ and $\mathcal{G}_{J_{\mathbf{m}}}$ respectively by adding the edge $(v,w)$ to exactly one of the restrictions when $(v,w)\not\in P$.

In particular, if $e = (v,w)$ simultaneously denotes this edge in $\mathcal{G}_S$ and $\mathcal{G}_{J_{\mathbf{m}}}$, there is a bijection between $\mathcal{P}_{S \cup J_{\mathbf{m}}}$ and $(\mathcal{P}_S \times \mathcal{P}_{J_{\mathbf{m}}}) \backslash (\mathcal{P}_S^{ne} \times \mathcal{P}_{J_{\mathbf{m}}}^{ne})$.

Note there are figures in the proof of Lemma <ref> which display the various possible local configurations of this gluing.

First we will show that for any pair of matchings $(P_S,P_{J_{\mathbf{m}}}) \in \mathcal{P}_S \times \mathcal{P}_{J_{\mathbf{m}}}$ such that the edge $(v,w)$ is included in $P_S$ or $P_{J_{\mathbf{m}}}$, there is a matching $P \in \mathcal{P}_{S \cup J_{\mathbf{m}}}$ formed by taking the union of $P_S$ and $P_{J_{\mathbf{m}}}$ and deleting an instance of $(v,w)$.
If we take a pair of $(P_S,P_{J_{\mathbf{m}}}) \in \mathcal{P}_S \times \mathcal{P}_{J_{\mathbf{m}}}$ such that $(v,w) \in P_S \cup P_{J_{\mathbf{m}}}$, we can see that all valence conditions are respected by the set $P := P_S \cup P_{J_{\mathbf{m}}} \backslash \{(v,w)\}$. We would violate Condition (<ref>) of Definition <ref> if $P$ contained $(v,w)$ and the edge $Y_{I_v}$. However, if $(v,w) \in P$, $(v,w) \in P_S$ and $(v,w) \in P_{J_{\mathbf{m}}}$, and since $P_{J_{\mathbf{m}}}$ is admissible we already know that the edge $Y_{I_v}$ cannot also be in $P_{J_{\mathbf{m}}}$. We would break Condition (<ref>) if $P_S$ contained the edge weighted $Y_{I_1^1(v)}$ and $P_{J_{\mathbf{m}}}$ contained the edge weighted $Y_{I_v}$. However, by Condition (<ref>) of Definition <ref>, including the edge $Y_{I_1^1(v)}$ in $P_S$ requires us to include all edges $Y_{I_i^1(v)}$ for $a_i(v) \in \mathcal{N}_v$, so by valence considerations the edge $(v,w_{\text{opt}})$ could not also be in $P_S$. In $\mathcal{G}_{J_{\mathbf{m}}}$, $w$ is valence $1 \oplus 0$ so $P_{J_{\mathbf{m}}}$ could also not include $(v_{\text{opt}},w)$, contradicting our assumption that the edge $(v,w)$ was in $P_S \cup P_{J_{\mathbf{m}}}$. To check that $P$ satisfies Conditions (<ref>) and (<ref>), it suffices to know that $P_S$ and $P_{J_{\mathbf{m}}}$ already satisfy this condition. For example, this gluing does not create any new pair of edges as in the hypothesis of Condition (<ref>).

Now, consider $P \in \mathcal{P}_{S \cup \Jm}$ with $(v,w)\in P$ and take the restrictions $P_S:= P \vert_{\mathcal{G}_S}$ and $P_{\Jm}:= P\vert_{\mathcal{G}_{\Jm}}$.  We wish to show that if $(v,w) \in P$, then $P_S \in \mathcal{P}_S$ and $P_{\Jm} \in \mathcal{P}_{\Jm}$, and if $(v,w) \not\in P$, then adding $(v,w)$ to one of $P_S,P_{\Jm}$ gives an element of $\mathcal{P}_S$ and an element of $\mathcal{P}_{\Jm}$.  These restrictions would not be admissible matchings if either they include too many or two few edges incident to $v$ or $w$ or if they broke one of the conditions of Definition <ref>.

We first address the admissibility conditions.  First,  suppose that $(v,w) \in P$,  so that $(v,w)$ is in both restrictions.  In $\mathcal{G}_{S \cup \Jm}$,  this edge is an internal edge while in $\mathcal{G}_S$ and $\mathcal{G}_{\Jm}$ this is a boundary edge.  The fact that $P$ satisfied Condition (<ref>) implies that the restrictions satisfy this condition as Condition (<ref>) is not about boundary edges.  Conditions (<ref>) and (<ref>) concern boundary edges, but since $(v,w)$ comes from an edge in $\Gamma$ so that $W((v,w)) = \emptyset$ and any diagonal $d$ has a nonempty label $W(d)$, there is nothing to check.  To check Condition (<ref>), notice that the edge $(v,w)$ in $\mathcal{G}_{J_{\mathbf{m}}}$ is always the edge $(v_\opt,w)$.  Therefore, the only other boundary edges that share a vertex with $(v_\opt,w)$ share vertex $v_\opt$.  However, vertex $w$ is not incident to a diagonal so none of these edges could  interact with $(v_\opt,w)$ as in Condition (<ref>).  Thus, Condition (<ref>) holds for $P\vert_{\mathcal{G}_{J_{\mathbf{m}}}}$.  The edge $(v,w)$ in $\mathcal{G}_{S}$ is not incident to any internal edges so Condition (<ref>) holds for this  restriction as well.  So in this case, the fact that $P$ is admissible implies that $P_S$ and $P_{\Jm}$ are both admissible.

Now, suppose that $(v,w) \notin P$.  We wish to show that we could add $(v,w)$ to exactly one of $P \vert_{\mathcal{G}_S}$ or $P\vert_{\mathcal{G}_{\Jm}}$ and have both sets of edges still satisfy Definition <ref>. Since $W((v,w)) = 1$ and all diagonals have nonempty label,  we automatically do not need to check admissibility Conditions (<ref>) and (<ref>).  In $\mathcal{G}_S$,  $(v,w)$ is a boundary edge which is either not incident to any internal edges, or is incident to $Y_{I_w}$.  Since $W(Y_{I_w})=I_w$ is not contained in the labels of any incident diagonals, we have nothing to check for admissibility Condition (<ref>) in $\mathcal{G}_S$. A similar argument holds for $\mathcal{G}_{\Jm}$. We would violate Condition (<ref>) if we added $(v,w)$ to $\mathcal{G}_{\Jm}$ and $Y_{I_v} \in P$,  or if $v$ is not covered by $w$, we added $(v,w)$ to $\mathcal{G}_S$, and $Y_{I_w} \in P$. If $v$ is not covered by $w$, the  the valence of $w$ in all three graphs is $1 \oplus 0$,  so we could not have both $Y_{I_v}$ and $Y_{I_w}$ in $P$.  Therefore,  in all cases we could add $(v,w)$ to one of the restrictions and preserve admissibility.

Now, we compare the number of edges incident to $v$ and $w$ in the restrictions with the valence of these vertices in both graphs. In all of our cases,  the valence of $v$ or $w$ in each of the smaller graphs will be of the form $a \oplus b$ where the vertex is incident to $a+b+1$ edges.  Therefore,  we will have too many edges incident to a vertex in the restriction only if the restriction includes every edge incident to this vertex.  This occurs if $P$ contains all edges incident to $v$ or $w$ which comes from $\mathcal{G}_S$ or $\mathcal{G}_{\Jm}$. By part (1) of Lemma <ref>, there cannot be such a matching $P \in \mathcal{P}_{S \cup \Jm}$.

In most of our cases,  the first component of the valence of $v$ or $w$ in the smaller graphs is 1, so in these cases,  we will not have enough edges incident to this vertex in the restriction if there are no edges incident to it. In order for this to occur,  we certainly have $(v,w) \notin P$ since otherwise $(v,w)$ would be in both restrictions.  Moreover,  if $(v,w) \notin P$, then we add $(v,w)$ to one of the restrictions.  Therefore, in order for this process to not include an edge incident to $v$ or $w$ in one of the restrictions, we must either have a situation as in statement (2) of Lemma <ref>, where no matter which restriction we add $(v,w)$ to, a vertex is unmatched, or a situation as in statement (3) of this lemma, where we have an uncovered vertex in a restriction, but we cannot add $(v,w)$ without violating another vertex's valence. As the lemma shows, we will never encounter such a matching of $\mathcal{G}_{S \cup \Jm}$.

We have one remaining way in which a restriction can include too few edges incident to a vertex. Suppose that $v \lessdot_{\mathcal{I}} w$ and $v = a_1^i(w)$ with $i > 1$, so that the edge $(v,w)$ in $\mathcal{G}_S$ is incident to $w_{\fix}$. Then, the valence of $w$ on this edge in both $\mathcal{G}_S$ and $\mathcal{G}_{S \cup \Jm}$ is $r \oplus 0$ for some $r$ possibly larger than 1 where  $w$ is adjacent to $r+2$ edges in $\mathcal{G}_{S \cup \Jm}$ and $r+1$ edges in $\mathcal{G}_S$. We would not be able to decompose $P \in \mathcal{P}_{S \cup \Jm}$ into admissible matchings of $\mathcal{G}_{S}$ and $\mathcal{G}_{\Jm}$ if $P$ included $Y_{I_v}$, the one edge incident to $w$ which lies only in $\mathcal{G}_{\Jm}$, did not include $(v,w)$, and included all edges incident to $v$ but not $w$ which lie in $\mathcal{G}_S$. This would mean that $w$ would not have enough incident edges in $P \vert_{\mathcal{G}_S}$ but we could not add $(v,w)$ to this set without violating the valence of $v$. However,  as before,  we would now include the edge $Y_{I_v}$ incident to $w$ and the edge $Y_{I_1^1(v)}$ incident to $v$,  which violates Condition (<ref>) of Definition <ref>. This completes our proof, as we have shown that any $P \in \mathcal{P}_{S \cup \Jm}$ can be decomposed into matchings of $\mathcal{G}_{S}$ and $\mathcal{G}_{\Jm}$.

The last statement in the lemma follows directly from the first two statements.

Now that we understand how the admissible matchings of a snake graph $\mathcal{G}_S$ compare with admissible matchings of the snake graphs that are glued together to make $\mathcal{G}_S$, we analyze the weighted sum of matchings which avoid the edges used in gluings.

In what follows, if $T$ is a disconnected set whose connected components are weakly rooted,  we define the snake graph $\mathcal{G}_T$ to simply be the a disconnected graph with connected components $\mathcal{G}_{T_i}$ for the connected components $T_i$ of $T$.  Given a weakly rooted set $S$ and $v \in \overline{S}$, it follows from the definition that the connected components of $S \backslash \{v\}$ are all weakly rooted. Note that a set $I \in \mathcal{I}$ is trivially weakly rooted as its rooted portion is the empty set. Recall that $Z(v) = \frac{Y_{I_v}}{\prod_{u \in \mathcal{C}_v} Y_{I_u}}$.

* Let $S$ be a weakly rooted set. Suppose there exists $w \in \overline{S}$ and $v \in N_\Gamma(w) \cap \Gamma^{\mathcal{I}}_{<w}$, $v \notin S$. Let $e$ be the boundary edge $(v,w)$ of $\mathcal{G}_S$. Then,

\[
\frac{1}{\ell(\mathcal{G}_S)}\sum_{P \in \mathcal{P}_S^{ne}} \wt(P) = \frac{1}{Z(v)\ell(\mathcal{G}_{S \backslash \{w\}})} \sum_{P \in \mathcal{P}_{S \backslash \{w\}}} \wt(P)
\]

where, if $S = \{w\}$, we set $\mathcal{P}_{\emptyset} = \{\emptyset\}$ and $\wt(\emptyset) = 1$.

* Let $w \in N_{\Gamma'}(v) \cap \Gamma^{\mathcal{I}}_{>v}$ and let $e$ be the boundary edge $(v,w)$ of $\mathcal{G}_{J_{\mathbf{m}}(v)}$. Then,
\[
\frac{1}{\ell(\mathcal{G}_{J_{\mathbf{m}}(v)})} \sum_{P \in \mathcal{P}_{J_{\mathbf{m}}}^{ne}} \wt(P) = Z(v) \cdot Y_{I^1_{m_1}} \cdots Y_{I^r_{m_r}}.
\]

(1) First, suppose that $\mathcal{G}_w$ is a subgraph of $\mathcal{G}_S$. We note in Corollary <ref> that, for the snake graph $\mathcal{G}_w$, there is a unique admissible matching which does not include $e$. By following the set of edges this matching includes, as in the proof of Lemma <ref>, we see that the weight of this matching divided by $\ell(\mathcal{G}_S)$ is $\frac{1}{Z(v)}$ and that this matching contains all edges of the form $(w,u)$ for $u \in N_\Gamma(w)$. Therefore, by Lemma <ref>, this matching can be combined with any matchings of the graphs $\mathcal{G}_{S_i}$ for the connected components $S_i$ of $S \backslash \{w\}$ and the claim follows.

Now, more generally we could have that $\mathcal{G}_w$ is not a subgraph of $\mathcal{G}_S$, but for some $J_{\mathbf{m}}(w) = \{w\} \cup I^1_{m_1}(w) \cup \cdots \cup I^r_{m_r}(w)$, $1 \leq m_i \leq c_i(w)+1$ for all $1 \leq i \leq \vert N_{\Gamma'}(w)\cap \Gamma^{\mathcal{I}}_{<w}\vert$, $\mathcal{G}_{J_{\mathbf{m}}(w)}$ is a subgraph of $\mathcal{G}_S$. Since $I_w \nsubseteq S$, there is at least one $i$ such that $m_i > 1$.  Here, the same logic as in the simpler case holds, but the matching of $\mathcal{G}_{J_{\mathbf{m}}(w)}$ which does not include $e$ includes the boundary edges which have weight $Y_{I_{m_j}^j(w)}$. When $m_i < c_i+1$, so that this weight is not 1, we do not glue onto these boundary edges, so we can use Lemma <ref> to again extend this admissible matching to one on the whole graph $\mathcal{G}_S$.

(2) The same logic for Corollary <ref> holds for a snake graph of the form $\mathcal{G}_{J_{\mathbf{m}}}$. The claim follows from evaluating the weights of the unique matching which does not use the edge $(v,w)$.

We will use strong induction on the size of $\vert \overline{S} \vert$.  The $\vert \overline{S} \vert = 1$ case was shown in Section <ref>,  so we assume $\vert \overline{S} \vert > 1$.

Let $v$ be a leaf in the subgraph $\overline{S}$ such that $v \neq m_{\mathcal{I}}(S)$.
Let $S'$ be the connected component of $S\setminus\{v\}$ containing $m_{\mathcal{I}}(S)$. It follows that the set $S \setminus S'$ is of the form $J_{\mathbf{m}}(v)$.  Since $v \in \bar{S}$, we know that, in $\mathbf{m} = (m_1,\ldots,m_{r)}$, at least one $m_i > 1$.

Notice that there exists $w \in \overline{S'}$ such that $(v,w) \in E(\Gamma)$. Since we assumed $v \neq m_{\mathcal{I}}(S)$, by the weakly rooted condition we know that $v<_{\mathcal{I}} w$.  Let $e$ simultaneously denote the edge $(v,w)$ in $\mathcal{G}_{S'}$ and $\mathcal{G}_{J_{\mathbf{m}}}$.  Then, by Lemma <ref>,  we can rewrite $\chi(\mathcal{G}_S)$ in the following way

\begin{align*}
\chi(\mathcal{G}_{S}) &= \chi(\mathcal{G}_{S' \cup J_{\mathbf{m}}}) \\&= \frac{1}{\ell(\mathcal{G}_{S' \cup J_{\mathbf{m}}})} \sum_{P \in \mathcal{P}_{S' \cup J_{\mathbf{m}}}} \wt(P) \\&= \frac{1}{\ell(\mathcal{G}_{S'})\ell(\mathcal{G}_{J_{\mathbf{m}}})} \bigg(\sum_{P \in \mathcal{P}_{S'}} \wt(P) \sum_{P \in \mathcal{P}_{J_{\mathbf{m}}}} \wt(P) - \sum_{P \in \mathcal{P}^{ne}_{S'}} \wt(P) \sum_{P \in \mathcal{P}^{ne}_{J_{\mathbf{m}}}} \wt(P) \bigg).
\end{align*}

By the inductive hypothesis, $Y_{S'} = \chi(\mathcal{G}_{S'})$ and $Y_{J_{\mathbf{m}}} = \chi(\mathcal{G}_{J_{\mathbf{m}}})$.  We can use Lemma <ref> to reduce the second term, to obtain the following,

\begin{align*}
\chi(\mathcal{G}_{S}) = Y_{S'} Y_{J_{\mathbf{m}}} - Y_{I_{m_1+1}^1(v)} \cdots Y_{I_{m_r+1}^r(v)}  \frac{1}{\ell(\mathcal{G}_{S' \backslash \{w\}})}\sum_{P \in \mathcal{P}_{S' \backslash \{w\}}} \wt(P) = Y_{S'} Y_{J_{\mathbf{m}}} -  Y_{J_{\mathbf{m}} \backslash \{v\}}Y_{S' \backslash \{w\}}
\end{align*}

where the last equality follows from invoking the inductive hypothesis on each connected component of $S' \backslash \{w\}$.
Finally,  we can now use Lemma <ref> to conclude $\chi(\mathcal{G}_S) = Y_S$.

§ COUNTING ADMISSIBLE MATCHINGS

We give a determinantal description of the number of admissible matchings of $\mathcal{G}_S$ for a weakly rooted set $S$.  For convenience, relabel $V(\Gamma)$ so that the vertices in $\overline{S}$ are numbered $1,\ldots,s$. For any $v \in \overline{S}$ with $\vert N_\Gamma(v)\cap\Gamma_{<v} \vert = r$, let $m_1,\ldots,m_r$ be minimal such that $\{v\} \cup I_{m_1}^1(v) \cup \cdots \cup I_{m_r}^r(v) \subseteq S$. Then, define $f(v) = 1 + (m_1 - 1) + \cdots + (m_r-1)$.
Let $N_S = (n_{i,j})$ be the $s \times s$ matrix defined by
\[
n_{i,j} = \begin{cases} f(i) & i = j \\ -1 & (i,j) \in E(\Gamma) \\ 0 & \text{ otherwise } \end{cases}
\]

This matrix is related to the $\mathfrak{N}$ matrix from Proposition 4.5 in <cit.>.

The number of admissible matchings of $\mathcal{G}_S$ for a weakly rooted set $S$ is equal to $\det(N_S)$.

We induct on $\vert \bar{S} \vert$, the size of the weakly rooted portion of $S$. First, suppose that $\bar{S} = \{v\}$, so that $S = J_{\mathbf{m}}(v)$. In our proof for Theorem <ref> for this case, following the reasoning for $S = \{v\}$ in Lemma <ref>, we see that, for each $1 \leq i \leq r$, there are $m_i-2$ admissible matchings which use an internal edge which shares vertices with diagonals $I_j^i$ and $I_{j+1}^i$ and one matching which uses the edge $Y_{I_{m_i-2}^i}$ incident to the diagonal $I_{m_i-1}^i$, and these sets of matchings are all distinct. There is one other matching besides these families which uses the edge weighted $Y_{I_v}$. Therefore, there are $(m_1-1) + \cdots + (m_r-1) + 1$ admissible matchings of $\mathcal{G}_{J_{\mathbf{m}}}$, showing the claim in this case.

Now, we consider a set $S$ such that $\vert \bar{S} \vert > 1$. We assume we have shown the claim for all sets with a strictly smaller weakly rooted portion. Let $v$ be a leaf in  $\bar{S}$, and let $w$ be the unique vertex in $\bar{S}$ adjacent to $v$. As in the proof of Theorem <ref> for the general case, let $S'$ be the connected component of $S \backslash \{v\}$ containing $m_{\mathcal{I}}(S)$ so that $S \backslash S' = J_{\mathbf{m}}(v)$ with at least one $m_i > 1$ in $\mathbf{m}$.  Then, since the $v$-th row of $N_S$ only has a $-1$ in column $w$ and $f(v)$ in column $v$ and similarly for the $v$-th column, we can compute

\begin{align*}
\det(N_S) &= f(v) \det(N_{S \backslash J_{\mathbf{m}}(v)}) - \det(N_{S \backslash (J_{\mathbf{m}}(v) \cup \{w\})})\\
&= \vert \mathcal{P}_{J_{\mathbf{m}}(v)} \vert \vert \mathcal{P}_{S \backslash J_{\mathbf{m}}(v)}\vert  - \vert \mathcal{P}_{S \backslash (J_{\mathbf{m}}(v) \cup \{w\})}\vert\\
\end{align*}

where the second equality follows from our inductive hypothesis.

From Lemma <ref>, we know that every admissible matching of $\mathcal{G}_S$ can be decomposed into an admissible matching of $\mathcal{G}_{S \backslash J_{\mathbf{m}(v)}}$ and of $\mathcal{G}_{J_{\mathbf{m}(v)}}$ where at least one matching uses the edge $e = (v,w)$. It follows from Lemma <ref> that $\vert \mathcal{P}_{J_{\mathbf{m}}(v)}^{ne} \vert = 1$ and  $\vert \mathcal{P}^{ne}_{S \backslash J_{\mathbf{m}}(v)} \vert = \vert \mathcal{P}_{S \backslash (J_{\mathbf{m}}(v) \cup w)} \vert$.
Therefore, we conclude that $\det(N_S) = \vert \mathcal{P}_S \vert$.

When $\Gamma$ is a path graph on $n$ vertices, the subalgebra of $\mathcal{A}_\Gamma$ spanned by variables of the form $Y_S, S \subseteq V(\Gamma)$ is a type $A_n$ cluster algebra by Corollary 6.2 in <cit.>. Then, up to reordering, the matrix $N_S$ has values $f(i)$ on the main diagonal and $-1$'s on the super and sub diagonal. Such a matrix is known as a continuant.  The determinant of such a continuant with entries $f(1),\ldots,f(s)$ on the main diagonal is given by the negative continued fraction $[[f(1),\ldots,f(s)]]$, defined by
\[
f(1) - \frac{1}{f(2) - \frac{1}{\ddots - \frac{1}{f(s)}}}.
\]

In this case, Theorem <ref> recovers a previously known formula for the number of perfect matchings of a surface snake graph $G_{\gamma}$.  To illustrate this, we briefly discuss the case of a cluster algebra from a polygon; for more general cluster algebras, one can take a suitable lift of the surface. Suppose $\gamma$ is a diagonal in a polygon with vertices $v_0,\ldots,v_{n-1}$ and triangulation $T$. Let $\gamma = (v_i,v_j)$ where, without loss of generality $i < j$. For all $i < k < j$, let $f_k$ denote the number of arcs from $T$ incident to $v_k$ which cross $\gamma$. Then, if $\mathcal{P}_\gamma$ denotes the set of perfect matchings of $\mathcal{G}_\gamma$,
\[
\vert \mathcal{P}_\gamma \vert = [[f_{i+1},\ldots,f_{j-1}]].
\]

This result can be seen as combining the theory of Conway-Coxeter's frieze patterns <cit.> with the connection between frieze patterns and cluster algebras of type $A$ <cit.>. More details on the correspondence are given in <cit.>.

§ ACKNOWLEDGEMENTS

The authors would like to thank Pavlo  Pylyavskyy for suggesting the original idea for this project and MRWAC 2020 for providing the setting for our initial collaboration.  We would also like to thank the Summer Research in Mathematics (SRiM) program hosted by SLMath (formerly MSRI) for their financial support and hospitality.

Esther Banaian was supported by Research Project 2 from the Independent Research Fund Denmark (grant no. 1026-00050B).  Elizabeth Kelley was supported by NSF Grant No. DMS-1937241.  Sylvester Zhang was partially supported by NSF Grants No. DMS-1949896 and No. DMS-1745638.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

titleA Generalization of Markov Numbers
journaltitlearXiv preprint arXiv:2210.07366

SIGMA. Symmetry, Integrability
Geometry: Methods

titleRooted Clusters for Graph LP Algebras
journaltitleSIGMA. Symmetry, Integrability and Geometry: Methods
and Applications

titleLattices from graph associahedra and subalgebras of the
Malvenuto–Reutenauer algebra
journaltitleAlgebra universalis

titleCluster algebras as Hall algebras of quiver representations
journaltitleCommentarii Mathematici Helvetici

Cambridge University Press

titleCluster algebras and continued fractions
journaltitleCompositio Mathematica

titleTriangulated polygons and frieze patterns
journaltitleThe Mathematical Gazette

titleMixed Dimer Configuration Model in Type $ D $ Cluster
Algebras II: Beyond the Acyclic Case
journaltitleThe Electronic Journal of Combinatorics

titleCluster algebras I: foundations
journaltitleJournal of the American mathematical society

titleLaurent phenomenon algebras
journaltitlearXiv preprint arXiv:1206.2611

Oxford University Press

titleLinear Laurent phenomenon algebras
journaltitleInternational Mathematics Research Notices

titleFarey boat: continued fractions and triangulations, modular
group and polygon dissections
journaltitleJahresbericht der Deutschen Mathematiker-Vereinigung

titleDouble dimer covers on snake graphs from super cluster
journaltitleJournal of Algebra

titleCluster expansion formulas and perfect matchings
journaltitleJournal of Algebraic Combinatorics

titlePositivity for cluster algebras from surfaces
journaltitleAdvances in Mathematics

titleHigher Dimer Covers on Snake Graphs
journaltitlearXiv preprint arXiv:2306.14389

titlePermutohedra, associahedra, and beyond
journaltitleInternational Mathematics Research Notices

titleThe Combinatorics of Frieze Patterns and Markov Numbers

titleA cluster expansion formula ($A_n$ case)
journaltitleThe Electronic Journal of Combinatorics

titleA Mixed Dimer Model for Type $D_n$ Cluster Algebras
journaltitleElectronic Journal of Combinatorics