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.

I have already tried for all the following 3-regular graphs


1 Answer 1


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.

enter image description here

Here's a more symmetric picture of this graph, with an induced $P_6$ highlighted:

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.