Existence of a pair of isomorphic subgraphs in a given graph with large number of edges

57 Views Asked by At

I am trying to show that a graph $G$ with $n$-vertices and $pn^2$ edges ($n\geqslant10$, and $p\geqslant10/n$) contains two vertex-disjoint and isomorphic subgraphs with at least $ap^2n^2$ edges, with $a$ a constant.

The solution I am trying to find involves the linearity of expectation but the computation of the probability for a random subgraph to be isomorphic to a given one seem complicated to compute.

Thank you for your help.