# Describe all graphs without a path of length 3

I have a problem with the following assignment.

Describe all graphs which do not contain a path whose length 3. Could you help me solve it?

-

With absolutely no conditions on the graph (you're not saying any), there are infinite: is the graph is not fully connected, you can just add isolated vertices.

If it's connected, there are infinite too, you can connect one vertex to as many as you want, so you have n+1 vertices, one of them of n degree, and the rest of 1 degree, you form a star.

Have in mind that you have to form the graph out of parts that are as much, 3 vertices forming a line, and you cannot connect more vertices to the outside vertices because you will have a path of length 3. So you can only connect more vertices to the middle one. Now, you can connect there, either one vertex, or another part of three, making the middle vertex be the same as the middle vertex in the previous graph: this is equivalente to connect two vertices to the middle, so the only thing you can do is, from an initial vertex, connect more vertices only to that vertex.

The conclusion is that the graph is formed by disconnected componentes formed by one vertex connected to k vertices of degree 1, with $k\in\mathbf{N}$

-

Hint: can you say anything about the degrees of the vertices of your graph? You might want to split the graph into connected components first.

-

You are looking for the graphs, whose connected components are stars. In particular, stars a trees with diameter at most 2, and all simple non-trees have diameter at least 3.

-

Typically this is considered the path of length 3:

Let's call it $P_3$. And we're looking for graphs that do not have a $P_3$ subgraph.

Any such graph is the union of connected components with each component having no $P_3$ subgraph.

Trivially, all connected graphs on $3$ or fewer vertices have no $P_3$ subgraph. (Note: this includes the triangle $K_3$, omitted from two of the previous answers.)

Now suppose a connected component has $\geq 4$ vertices.

• Claim: This component must be a tree. Otherwise it either contains a subgraph isomorphic to

which contains a $P_3$ subgraph (as highlighted), or a cycle $C_k$ for $k \geq 4$, which contain $P_3$ subgraphs. In either case, we reach a contradiction.

• Claim: There is a unique vertex of degree $\geq 2$.

Otherwise there is a path between two vertices $i$ and $j$ of degree $\geq 2$, which together form a subgraph that contains a $P_3$ subgraph (there's a few cases to check here; I'll omit the painful details), giving a contradiction.

Hence any connected component with $4$ or more vertices is a star (i.e., $K_{1,k}$ for $k \geq 3$).

Hence, the graphs without subgraphs isomorphic to $P_3$ are the union of graphs in $$\{K_1,K_2,K_3\} \cup \{K_{1,k}: k \geq 2\}.$$

-