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