(* Here, a brute-force search is conducted in order to check the results of the algorithm. The files trees**.g6 can be downloaded from Gordon Royle's webpage: http://people.csse.uwa.edu.au/gordon/remote/graphs/index.html *)

<<Combinatorica`

SetDirectory["C:\\Documents and Settings\\swagner\\My Documents\\MerrifieldSimmons"]

MerrifieldSimmons[g_]:=MerrifieldSimmons[g]=Which[V[g]==0,1,V[g]==1,2,True,MerrifieldSimmons[DeleteVertex[g,1]]+MerrifieldSimmons[DeleteVertices[g,Neighborhood[g,1,1]]]];

goptlist={};msoptlist={};
Do[l=Import[StringJoin["trees",If[k<10,"0",""],ToString[k],".g6"],"Table"];gopt={};msopt=0;Do[g=FromAdjacencyMatrix[ImportString[l[[j,1]],{"Graph6","AdjacencyMatrix"}][[1]]];If[Max[Degrees[g]]≤4,m=MerrifieldSimmons[g];If[msopt==m,Append[gopt,g]];If[msopt<m,gopt={g};msopt=m]],{j,1,Length[l]}];goptlist=Append[goptlist,gopt];msoptlist=Append[msoptlist,msopt];Export["gopt.m",goptlist];Export["msopt.m",msoptlist],{k,1,20}]

msoptlist

goptlist