# Maximum number of induced $P_3$ in a $P_4$-free graph

Say I have a graph $G$ on $n$ vertices that is $P_4$-free (it has no induced paths of length 4). These are known as cographs. Note that $G$ might not be connected.

I'd like to list the induced $P_3$ in $G$. That is, I want to find the list of all vertex triples $\{a,b,c\}$ that induce a path of length 3, meaning that exactly one edge is missing between these 3.

My question is : at most how many $P_3$ will I have in the list, in big-O notation ?

An obvious upper bound is ${n \choose 3} \in O(n^3)$ induced $P_3$. However I haven't been able to construct a $P_4$-free graph having that many. So are there possibly $O(n^2)$ ?

I'd also be interested in an algorithm that finds all $P_3$ quickly.

And as a side question, should we write the plural of $P_3$ as "$P_3$s" ?

In the complete bipartite graph $K_{n,n}$ every vertex is the center of ${n\choose 2}$ different $P_3$'s and there are $2n$ vertices, so this certainly qualifies for $O(n^3)$.
For the algoritm I would also simply take each vertex as the center and list its neighbour pairs. Since the output has size $O(n^3)$ this must be approximately optimal.
Since I am not english I won't guess how you write the plural of $P_3$, but I do it the way you can see earlier in this answer :)
• Yes thank you ! I was kind of hoping to avoid having to look at $O(n^3)$ sets of vertices but it seems it can't be avoided in general. Oh well, thanks again ! May 30 '14 at 5:29
• I usually see the same notation: $P_3$'s. May 30 '14 at 17:41