the answer: _
G P4-free, both G, G connected with min n(G)
___
G-v P4-free, so one of G-v and G-v is disconnected
_
if G_v disconnceted, then v isolated in G......#
___
可是还有一个case: 要是 G-v connected 当然 G-v disconnected.
ex: C4
join
或许你可以假设 G-v= ▽ G_i, then
___
1. v 至少会连到一个 component of G-v,since G connected
_
2. 而且每个G_i都会有一点不连到v, since G connceted
再由此去找出P4, 得到矛盾.
p.s.我的做法是证明:
If G connctedand P4-free, then G is a complete bipartite graph.