## 3 A Lower Bound on Listing  
[PERSON] and [PERSON] [2] describe an algorithm for finding complete subgraphs of size \(s\). If the host graph has an arboricity \(a\), they show that their algorithm runs in \(\mbox{O}(sma^{s-2})\) time, where \(m\) is the number of edges in the host graph. Since a tree with \(n\) nodes always has \(n-1\) edges, a graph with arboricity \(a\) always has less than \(an\) edges, so for a constant \(a\), this is essentially linear time. We show that this upper bound for the running time cannot be extended to general pattern graphs. If the pattern graph is connected but not complete, it is possible to find a sequence of host graphs containing a number of induced subgraphs isomorphic to the pattern graph that is quadratic in the number of nodes. It follows that there is no algorithm that lists all of them in less than quadratic time. We start by proving that every graph, unless it is complete or disconnected, has three nodes connected in a V-shape--two of them connect to the third but not to each other. Knowing that, we can create multiple copies of the end nodes of the V-shape, in a way that does not increase the arboricity. That gives us a graph with many subgraphs isomorphic to the original graph. If there are \(n\) copies of each of those two nodes, we can combine them in \(n^{2}\) ways. **Theorem 1**. : _If a pattern graph is connected and not complete, there is no algorithm that lists all occurrences of that pattern in a host graph with constant arboricity in a time that is subquadratic in the number of nodes._  
**Lemma 2**. : _If a graph is connected but not complete, there is always a V-shaped induced subgraph; that is, there are always nodes \(A\), \(B\) and \(C\) such that there are edges \(AB\) and \(BC\) but not \(AC\)._  
Proof. : Let \(G\) be a graph with \(n\) nodes. For \(n\leq 3\), the theorem holds trivially. For \(n>3\), inductively assume that the lemma holds for \(n-1\). \(G\) can be seen as the union of a graph \(\gamma\) with \(n-1\) nodes and a single node \(\
u\). We may assume w.l.o.g. that \(\gamma\) is either complete or not connected. Suppose \(\gamma\) is complete. If \(\
u\) connects to all nodes in \(\gamma\), then \(G\) is complete. If \(\
u\) does not connect to any node in \(\gamma\), then \(G\) is not connected. If there is a node \(\alpha\) that \(\
u\) connects to, and a node \(\beta\) that \(\
u\) does not connect to, then \(\{\
u,\alpha,\beta\}\) induces a V-shaped subgraph in \(G\). Suppose \(\gamma\) is not connected. There are two subgraphs \(\gamma_{1}\) and \(\gamma_{2}\) in \(\gamma\) with no edge between them. If \(\
u\) is not connected to any of these two subgraphs, then \(G\) is not connected. Otherwise, there is a node \(\alpha\) in \(\gamma_{1}\) and a node \(\beta\) in \(\gamma_{2}\), both connected to \(\
u\). Then \(\{\
u,\alpha,\beta\}\) induces a V-shaped subgraph in \(G\). By induction the lemma holds for all \(G\). **Lemma 3**. : _If a graph \(P\) has a V-shaped induced subgraph, there exists a sequence of graphs \(\mbox{\rm G}(n)\) with constant arboricity and \(\mbox{\rm O}(n)\) nodes such that the number of induced subgraphs of \(\mbox{\rm G}(n)\) isomorphic to \(P\) is \(\Omega(n^{2})\)._  
Proof. : Suppose that \(\{A_{1},B,C_{1}\}\) induce a V-shaped subgraph in \(P\); \(A_{1}\) and \(C_{1}\) form edges with \(B\) but not with each other. Let \(D\) be the subgraph of \(P\) resulting from removing the nodes \(A_{1}\) and \(C_{1}\), and let \(\mbox{\rm G}(1)\) = \(P\). Next, let \(\mbox{\rm G}(n+1)\) be a graph based on \(\mbox{\rm G}(n)\), with two more nodes; one node \(A_{n+1}\) that connects to the same nodes as \(A_{1}\) in \(\mbox{\rm G}(n)\), and one node \(C_{n+1}\) that connects to the same nodes as \(C_{1}\) in \(\mbox{\rm G}(n)\). The number of nodes in \(\mbox{\rm G}(n)\) is then \(|P|+2n-2\), which is \(\mbox{\rm O}(n)\). Let \(\mbox{\rm H}(a,c)\) be the subgraph of \(\mbox{\rm G}(n)\) induced by \(\{A_{a},C_{c}\}\) and the nodes of \(D\). \(\mbox{\rm H}(a,c)\) is isomorphic to \(P\).