## 2 Materials and Methods
### Preliminary
#### 2.1.1 Multigraphs and Graphs  
Let \(\mathbb{R}\) and \(\mathbb{Z}\) denote the sets of reals and non-negative integers, respectively. For two integers \(a\) and \(b\), let \([a,b]\) denote the set of integers \(i\) with \(a\leq i\leq b\). Multigraphs  
A _multigraph_ is defined to be a pair \((V,E)\) of a vertex set \(V\) and an edge set \(E\) such that each edge \(e\in E\) joins two vertices \(u,v\in V\) (possibly \(u=v\)) and the vertices \(u\) and \(v\) are called the _end-vertices_ of the edge \(e\), and let \(V(e)\) denote the set of the end-vertices of an edge \(e\in E\), where an edge \(e\) with \(|V(e)|=1\) is called a _loop_. We denote the vertex and edge sets of a multigraph \(M\) by \(V(M)\) and \(E(M)\), respectively. A path with end-vertices \(u\) and \(v\) is called a \(u,v\)_-path_, and the length of a path is defined to be the number of edges in the path. Let \(M\) be a multigraph. An edge \(e\in E(M)\) is called _multiple_ (to an edge \(e^{\prime}\in E(M)\)) if there is another edge \(e^{\prime}\in E(M)\) with \(V(e)=V(e^{\prime})\). For a vertex \(v\in V(M)\), the set of neighbors of \(v\) in \(M\) is denoted by \(N_{M}(v)\), and the _degree_\(\deg_{M}(v)\) of \(v\) is defined to be the number of times an edge in \(E(M)\) is incident to \(v\); i.e., \(\deg_{M}(v)=|\{e\in E(M)\mid v\in V(e),|V(e)|=2\}|+2|\{e\in E(M)\mid v\in V(e ),|V(e)|\ =\ 1\}|\). A multigraph is called _simple_ if it has no loop and there is at most one edge between any two vertices. We observe that the sum of the degrees over all vertices is twice the number of edges in any multigraph \(M\); i.e.,  
\[2|E(M)|=\sum_{v\in V(M)}\deg_{M}(v).\]  
For a subset \(X\) of vertices in \(M\), let \(M-X\) denote the multigraph obtained from \(M\) by removing the vertices in \(X\) and any edge incident to a vertex in \(X\). An operation of _subdividing_ a non-loop edge (resp., loop) \(e\in E(M)\) with \(V(e)=\{v_{1},v_{2}\}\) (resp., \(V(e)=\{v_{1}=v_{2}\}\)) is to replace \(e\) with two new edges \(e_{1}\) and \(e_{2}\) incident to a new vertex \(v_{e}\) such that each \(e_{i}\) is incident to \(v_{i}\). An operation of _contracting_ a vertex \(u\) of degree 2 in \(M\) is to replace the two edges \(uv\) and \(uv^{\prime}\) incident to \(u\) with a single edge \(vv^{\prime}\) removing vertex \(u\), where the resulting edge is a loop when \(v=v^{\prime}\). The _rank_\(\operatorname{r}(M)\) of a multigraph \(M\) is defined to be the minimum number of edges to be removed to make the multigraph acyclic. We call a multigraph \(M\) with \(\operatorname{r}(M)=k\) a _rank-\(k\) graph_. Let \(V_{\deg,i}(M)\) denote the set of vertices of degree \(i\) in \(M\). The _core_\(\operatorname{Cr}(M)\) of \(M\) is defined to be an induced subgraph \(M^{*}\) that is obtained from \(M^{\prime}:=M\) by setting \(M^{\prime}:=M^{\prime}-V_{\deg,1}(M^{\prime})\) repeatedly until \(M^{*}\) contains at most two vertices or consists of vertices of degree at least 2. The core \(M^{*}\) of a connected multigraph \(M\) consists of a single vertex (resp., two vertices) if and only if \(M\) is a tree with an even (resp., odd) diameter. A vertex (resp., an edge) in \(M\) is called a _core vertex_ (resp., _core edge_) if it is contained in the core of \(M\) and is called a _non-core vertex_ (resp., _non-core edge_) otherwise. The _core size_\(\operatorname{cs}(M)\) is defined to be the number of core vertices of \(M\), and the _core height_\(\operatorname{ch}(M)\) is defined to be the maximum length of a path between a vertex \(v\in V(M^{*})\) to a leaf of \(M\) without passing through any core edge. The set of non-core edges induces a collection of subtrees, each of which we call a _non-core component_ of \(M\), where each non-core component \(C\) containsexactly one core vertex \(v_{C}\) and we regard \(C\) as a tree rooted at \(v_{C}\). Let \(C\) be a non-core component of \(M\). The _height_\(\operatorname{height}(v)\) of a vertex \(v\) in \(C\) is defined to be the maximum length of a path from \(v\) to a leaf \(u\) in the descendants of \(v\).