Enumeration of perfect matchings of the middle graph of a graph \(G\) with \(\triangle (G) \leq 4\) (Q6197712)

For a graph \(G\), the middle graph \(M(G)\) is obtained as follows: first, insert a new vertex on each of the edges of \(G\). Second, connect those newly inserted vertices by an edge that correspond to adjacent edges of \(G\). In other words, the vertex set of \(M(G)\) is \(V(G) \cup E(G)\), and the edge set consists of all pairs \(ve\) with \(v \in V(G)\) and \(e \in E(G)\) such that \(v\) is one of the ends of \(e\), and all pairs \(ef\), where \(e,f \in E(G)\) are adjacent edges of \(G\). In this paper, the authors prove an elegant general formula for the number of perfect matchings in the middle graph of a graph \(G\) whose maximum degree is at most \(4\): if \(G\) is a connected graph with \(\Delta(G) \leq 4\), \(n\) vertices and \(m\) edges, such that \(m+n\) is even, then \(M(G)\) has precisely \(2^{m-n+1}3^{(m-n)/2}\) perfect matchings. In particular, the number of perfect matchings in \(M(G)\) is \(2^{n/2+1}3^{n/4}\) for connected cubic graphs \(G\) (such that \(4 \mid n\)), and \(2^{n+1}3^{n/2}\) for connected \(4\)-regular graphs (\(n\) even).