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

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.

• There is only one connected component containing a vertex. It doesn't seem like what you are saying is what you really want to ask. – plop Jul 14 at 20:34
• What I meant is: find the subset (with max edges) of the connected component, among all the possible subset of size m of the connected component. I'm not sure about the exact terminologies. – Mamun Jul 14 at 20:40
• @plop Please see if the edited question makes sense now. – Mamun Jul 14 at 21:04
• @Mamun All above comments have become outdated since my edit. – John L. Jul 16 at 6:04
• @D.W, can you remove all above comments? Thanks. – John L. Jul 16 at 6:04

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).