Let G be a connected simple graph with a vertex set V, an edge set E. Let G_σ be a graph G with a partial assignment maps from a subset U of V into the real number R. For a given G_σ, an assignment λ from V into R such that λ(u)=σ(u) for each u in U, is called an extension of σ on G. For an extension λ of σ, we define the length L_λ(e) of an edge e={u,v} on λ by |λ(u)－λ(v)|, the length L_λ(G_σ) of G_σ on λ by Σ_e in E L_λ(e), respectively. Furthermore, L^*(G_σ) is defined by the minimum value of L_μ(G_σ) for any extension μ of σ, and an extension λ of σ such that L_λ(G_σ)=L^*(G_σ) is called an most-parsimonious extension (abbreviated to MPE) on G_σ. We call the problems on this minimization the MPE problems.

From a mathematical point of view, D. F. Robinson (1973) has introduced these problems, and shown a polynomial time algorithm on the number of vertices for obtaining a MPE. On the other hand, from a phylogenetic point of view, J. M. Farris (1970), D. L. Swofford and W. P. Maddison (1987) have dealt with the problems on completely bifurcating phylogenetic trees and shown a solution. M. Hanazawa et al. (1995) have mathematically formulated the problems for the case of which G is a tree, and presented clear algorithms for those. Note that we have a gap between the Robinson method and the Hanazawa et al. one. Therefore, M. Hanazawa and H. Narushima (1999), K. Miyakawa and H. Narushima (2008) have extended the MPR problems for the case of which G is a graph having only one cycle, called a unicycle graph, and shown a linear time algorithm for solving the problems. In this paper, we deal with the MPE problems for a graph which consists of a complete graph and some trees, called a branching trees clique, and show some propositions.