# Finding a 3-regular graph “with least no. of vertiecs” containing P6 as an induced-subgraph

Can you tell me a 3-regular graph with the least no of vertices, that contains P-6 as an induced subgraph?

A 3-regular graph is one in which the degree of every vertex is 3.

P-6 looks like: o--o--o--o--o--o

H is an induced subgraph of G if the vertex set of H is a subset of the vertex set of G and uv is an edge connecting vertices 'u' and 'v' in H only if uv is an edge in G.

The main problem is the 'least no. of vertices' clause.

I have already tried for all the following 3-regular graphs and have found that none of these graphs contain P6 as an induced subgraph. So the order of the graph has to more than 8 for sure. The vertices of the induced $$P_6$$ have degrees $$1, 2, 2, 2, 2, 1$$ in the path, and need to have total degree $$3,3,3,3,3,3$$, so they need $$2+1+1+1+1+2=8$$ edges more coming out of them. None of these can go to other vertices in the $$P_6$$, because it's induced, so they need to go to other vertices in the graph.
These $$8$$ edges need at least $$\lceil \frac83 \rceil = 3$$ vertices to go to. But we can't have just $$3$$ other vertices, because there is no $$3$$-regular graph on $$9$$ vertices. (The handshake lemma says that such a graph would have $$\frac{3\cdot 9}{2} = 13.5$$ edges.) So we must have at least $$4$$ other vertices.
With $$4$$ other vertices, their total degree must be $$4 \cdot 3 = 12$$, so they need to take the $$8$$ edges coming out of the $$P_6$$, and have $$2$$ more internal edges. (Each internal edge contributes $$2$$ to the sum of their degrees.) There are plenty of ways to do this; one of them is shown below. Here's a more symmetric picture of this graph, with an induced $$P_6$$ highlighted: 