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.