8 Example: Let G be a simple graph. If G has n vertices, e edges, and o connected components then n-≤e≤(n-)n-O+1) Proof: e>n-o Let us apply induction on the number of edges of G. e=0, isolated vertex, has n components, n=o 0=e>n-0=0, the result holds Suppose that result holds for e=eo-1 Omitting any edge (G has n vertices, o components and eo-1 edges. (2)G has n vertices, @+1 components and eo-1 edges❖ Example: Let G be a simple graph. If G has n vertices, e edges, and ω connected components , then ( )( 1) 2 1 n −  e  n − n − + Proof: e≥n-ω Let us apply induction on the number of edges of G. e=0, isolated vertex，has n components ，n=ω, 0=e≥n-ω=0，the result holds Suppose that result holds for e=e0 -1 e=e0 , Omitting any edge , G', (1)G' has n vertices, ω components and e0 -1 edges. (2)G' has n vertices, ω+1 components and e0 -1 edges