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: