Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Thanks for nice reference! But I cannot understand his paper since it's written in Deutsch... Can you explain a brief sketch of the proof? If it is not easy, I may post another question about it.
Nice proof! Actually, I found another proof by infinite descent about the square of the number of $c_1$ and $c_2$ edges appearing at the start and the end of such path. But I think your one is much more intuitive. Thank you.
Intuitively, I understood that adding $v$ makes $(r-1)$-cliques in $G[N(v)-v]$ to $r$-cliques in $G$. But how can I prove this concretely? Should I focus on the fact that $N(v)$ makes a clique, and adding $v$ to $N(v)$ makes a clique with one more vertex?
But how about this case: $G$ has one non-path component $G_0$ such that $\vert E(L(G_0)) \vert=\vert E(G_0)\vert + m$, and sufficiently many path components $G_1 \cdots G_{m+1}$. Then $\vert E(G) \vert = \vert E(L(G)) \vert+1$ since $\vert E(G_i) \vert = \vert E(L(G_i)) \vert+1$. What can we say about it?
