Affirming a conjecture of Erdos and Renyi we prove that for any (real number) c(1) > 0 for some c(2) > 0, if a graph G has no c(1) (log n) nodes on which the graph is complete or edgeless (i.e., G exemplifies G negated right arrow (c(1) log n)(2)(2)), then G has at least 2(c2n)non-isomorphic (induced) subgraphs. (C) 1998 Academic Press. [References: 6]
展开▼
机译：肯定了鄂尔多斯和仁义的猜想，我们证明了对于任何（实数）c（1）> 0，对于某些c（2）> 0，如果图G没有该图的c（1）（log n）个节点是完整的或无边的（即，G表示 G 否定右箭头（c（1）log n）（2）（2）），则G至少具有2（c2n）个非同构（诱导）子图。 （C）1998年学术出版社。 [参考：6]
展开▼
