孙博告诉我的,求证
在任意简单有向图$ G(V,E)$ 中,存在一个顶点$ v$ ,使得$ |N^2(v)|\geq 2|N(v)|$ ,其中$ N(v)=\{u\in V:(v,u)\in E\}$ , $ N^2(v)=\{u\in V:(v,u)\in E \vee\exists w\in V, (v,w)\in E,(w,u)\in E\}$ 。
通俗得讲就是在一个简单有向图中存在一个顶点,走至多两步能达到的顶点数至少为走一步能达到的顶点数的 2 倍。
注:简单有向图指任两点之间至多一条边。
看上去蛮简单的,事实上很不好做,是一个 OPEN 多年的问题...
Q. E. D.