Combinatorial proof of formula for the number of connected induced sub-graphs in the n-helm graph.
=================================================================================================

The n-helm graph has 2n+1 vertices and 3n edges and is composed of:
    a central vertex, 
    n inner vertices arranged in a cycle and connected to the central vertex,
    n outer vertices connected to a neighboring inner graph.

There are four cases to consider.

Case subgraph includes the central vertex:
  Then for each spoke subgraph includes one of
	a) no vertices
	b) inner vertex only
	c) inner and outer vertex
  => 3^n.

Case subgraph does not include the central vertex but includes all inner cycle vertices:
   Then for each spoke the subgraph can either include the outer vertex or not.
  => 2^n.

Case subgraph does not include the central vertex but includes a connected range of inner cycle vertices of length k with 1<=k<n:
   Then the range may begin on any of the n inner vertices and for each spoke in the the range the subgraph can either include the outer vertex or not.
  => n * Sum_{k=1..n-1} 2^n = n*(2^n-2).

Case subgraph includes neither any inner cycle vertices nor the central vertex:
  Then the subgraph must contain exactly one of the outer vertices.
  => n.

Total:
a(n) = 3^n + 2^n + n*(2^n-2) + n
     = 3^n + (n+1)*2^n - n.