2 problems

Let $\EuScript{G}(n,p)$ be a random simple undirected graph with $n$ vertices and edge-probability $0\leq p\leq 1$. For $c>1$, assume $c\log(n)/n<p(n)<1-o(\log(n)/n)$. Square-free…

Regular-graph complexity conjecture. If $c(G)<1$, then $G$ is either isomorphic to $C_7$, or there is an integer $n\geq2$ such that $G$ is isomorphic to either $K_{n,n}$ or…