# What is the smallest graph that contains all non-isomorphic 4-node and 5-node connected graphs as induced subgraphs?

I'm looking for an undirected graph $G$ which contains as induced subgraphs:

• the six $4$-node connected graphs and,
• the twenty one $5$-node connected graphs.

Ideally, I would also like it to be as small as possible (least number of nodes). If we take the union of these graphs, it has $6 \times 4+21 \times 5=129$ nodes. If we take the graphs and identify them at a point, it has $6 \times 4+21 \times 5-(6+21)+1=103$ nodes.

This would be helpful for testing our program for network motif detection program (NetMODE), which searches for connected induced subgraphs in networks.

If it helps, I've attached a picture of the graphs below: • Each of the graphs with 4 nodes can be produced from one of the graphs of 5 nodes by removing a node, therefore any graph containing all 5 node connected graphs will also contain all 4 node connected graphs. If a 5 node graph has x arcs and x<9 then a 5-node graph with x+1 arcs can be made by removing a node of degree n and replacing with a node of degree n+1. Sometimes more than one x+1 graph can be made from one x graph, or more than one x graph makes the same x+1 graph, but at least I can deduce that the smallest G has at most 5*(21-(10-4))+(10-4)+5=86 nodes. – Angela Richardson Oct 24 '11 at 5:38
• The smallest graph which contains all of the 4-vertex graphs has 7 vertices, and there are actually 77 such graphs (from a calculation with Maple). – jp26 Oct 24 '11 at 15:59
• Plus there is a graph with 8 vertices and 16 edges which contains 19 of the 21 5-vertex graphs, so I would conjecture that there will be a graph with 9 vertices which meets your needs... – jp26 Oct 24 '11 at 17:20

Surprisingly, the answer is 7 vertices for all 4-vertex subgraphs and 9 vertices for all 5-vertex subgraphs. I checked all graphs with 8 vertices and this was the first one (and only one so far) with 9 vertices that I found: This is the listing of each of the 21 different subgraphs with 5 vertices: This is a graph which contains all the graphs with 4 vertices: That is, $K_4 : \{a,b,c,d\}$, $K_4-e : \{ a,b,c,e \}$, $C_4 : \{a,b,e,f \}$, $P_4 : \{ c,d,e,f \}$, $K_{1,3} : \{b,e,f,g\}$ and the final one $\{b,c,d,f\}$.

And this is a graph with 10 vertices which contains all connected graphs with 5 vertices: This is all of the different subgraphs of the latter graph: I'll continue the search for a 9 vertex graph overnight, but I'm now doubting it can exist. I can also update my answer with the Maple code if anyone is interested.

Even with the exponential increase in number of small subgraphs, there are so many graphs that I'd like to believe that there would be a graph with all subgraphs on $k$ vertices which isn't exponential in $k$. (but I would be wrong!)

• I wouldn't mind seeing the maple code. Feel free to put it somewhere and link from the answer if it would clutter the answer. – Jack Schmidt Oct 24 '11 at 20:47
• Not sure how to make code look nice, but here's the base code. Call it for a maple graph G with: DrawGraph(fiveinlist(G, Glist5)); with(GraphTheory): Glist5:=[NonIsomorphicGraphs(5,output=graphs,outputform=graph,restrictto=connected)]: fiveinlist := proc (G, Glist) local S, bl, ts, l, ns; ts := []; for S in Glist do ns := 0; bl := 0; for lsubs in combinat[choose](Vertices(G), NumberOfVertices(Glist)) do if IsIsomorphic(InducedSubgraph(G, lsubs), S) then ns := 1; bl := lsubs end if end do; if ns = 1 then ts := [op(ts), InducedSubgraph(G, bl)] end if end do; RETURN(ts) end proc; – jp26 Oct 24 '11 at 21:41
• thanks. Do you have the code to make your specific G as well? (Sorry part of this is just to learn how to do reasonable things with graphs in maple.) Did you just search through random graphs on 10 vertices and are now searching 9 vertices exhaustively? – Jack Schmidt Oct 24 '11 at 21:48
• (ok, got the "four" one done at least) – Jack Schmidt Oct 24 '11 at 21:54
• I made that graph with: G5 := Graph(8); G5 := AddEdge(G5, {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 8}, {3, 4}, {3, 5}, {4, 7}, {6, 7}, {7, 8}}); G5b := AddVertex(G5, 9, inplace = false); AddEdge(G5b, {{5, 9}, {8, 9}}); G5c := AddVertex(G5b, 10, inplace = false); AddEdge(G5c, {{1, 10}, {2, 10}, {3, 10}, {4, 10}}); – jp26 Oct 24 '11 at 22:28

The size of a graph that contains all $k$-vertex subgraphs as induced subgraphs is exponential in $k$.

There are more than $2^{\binom{k}2}/k!$ graphs on $n$ vertices. So if $X$ is a graph on $n$ vertices that contains all $k$ vertex subgraphs as induced subgraphs then $$\binom{n}{k} \ge 2^{\binom{k}2}/k!$$ and as $$\binom{n}{k} \le \frac{n^k}{k!}$$ we have $$n^k \ge 2^{\binom{k}2}.$$ So $$k\, \log_2(n) \ge k(k-1)/2$$ and therefore $n \ge 2^{(k-1)/2}$.

Let $p$ be a prime congruent to 1 mod 4. The vertices of the Paley graph are the integers mod $p$; two integers are adjacent if their difference is a square mod $p$. The Paley graph on $p$ vertices contains all graphs on $k$ vertices as induced subgraphs, where $k\approx c\,\log_2(p)$.