We pick an arbitrary root to regard it as a rooted tree, and perform tree DP.

Note that, since the subgraph of the tree must form another tree, once the vertex subset is fixed, the edge set is unique (if any). Thus we will identify a subgraph that forms a tree and its vertex set (that yields a tree by choosing edges appropriately).

We call a graph (with one or more vertices) general alkane if and only if:

• the graph is an undirected tree, and
• every vertex has a degree \(1\) or \(4\),

where we ignored the necessity of the existence of a degree-\(4\) vertex. A graph is an alkane if and only if the graph has \(5\) or more vertices and is a general alkane, so it is sufficient to find the maximum vertices in a general alkane.

For a non-root vertex \(v\), let \(dp_v\) be the maximum number of vertices in a subtree consisting of ancestors of \(v\) (possibly including \(v\) itself) such that adding \(v\) results in a general alkane.

We consider how to compute the DP (Dynamic Programming).

Suppose that we have already evaluated all the ancestors of \(v\) (except for \(v\)). How can we compute \(dp_v\)?

We consider the following two cases: when \(v\)’s degree is \(1\) and \(4\).

If \(v\)’s degree is \(1\), only \(v\)’s parent is adjacent to \(v\), so the number of vertices is \(1\).

If \(v\)’s degree is \(4\), then the vertices adjacent to \(v\) is \(v\)’s parent and three children of \(v\), so \(v\) must have at least \(3\) children. If it does, we can pick children \(u_1\), \(u_2\), and \(u_3\), together with, for each of the children, a vertex set to which adding the parent \(v\) of the child forms a general alkane. By maximizing the number of vertices in those vertex sets by picking three children \(u\) with largest values of \(dp_u\), we can obtain a conforming vertex set with \((dp_{u_1} + dp_{u_2} + dp_{u_3} + 1)\) vertices.

Now we can use the results above to find the answer.

If a subgraph is a general alkane, the most deep vertex is uniquely determined. Let \(v\) denote this vertex, and do casework depending on the degree of \(v\).

If \(v\)’s degree is \(1\), then the maximum number of vertices is \(dp_u + 1\), where \(u\) is the vertex adjacent to \(u\).

If \(v\)’s degree is \(4\), then the maximum number of vertices is \(dp_{u_1} + dp_{u_2} + dp_{u_3} + dp_{u_4} + 1\), where \(u_1, u_2, u_3\), and \(u_4\) are children of \(v\). Note that \(v\) must have at least four children.

The answer can be found by computing it for each \(v\). The time complexity is \(O(N)\).