Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 5 down vote accepted

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}$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Typically this is considered the path of length 3:

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.)

$K_3$

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

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

    $K_3$ with a pendant vertex

    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\}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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