Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex

Question

Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to find the connected subgraph (not sure about this terminology) with maximum number of edges, among all the connected subgraph of $C$ that satisfy the following:

1. includes vertex $v_1$
2. has exactly $m$ number of vertices (including $v_1$)

By connected subgraph of $C$, I mean a subgraph of $C$, such that each pair of vertices in it are connected by a path.

Answer 1

It's NP-hard (by reduction from clique problem).

Let $G$ be an arbitrary graph, and we want to check if there exists a clique of size $m-1$ in this graph. This problem is NP-hard. By adding $v_1$ to the graph and connecting it to all vertices in $G$, we reduce the clique problem to your problem (since clique, when exists, has the maximum number of edges).