Discrete Mathematics

Discrete Mathematics

Table of Contents
1........................................................................................................................................................1
2........................................................................................................................................................2
3........................................................................................................................................................4
4........................................................................................................................................................6

1.
Theorem – A graph with v vertices and e edges has at least v – e connected components.
Proof: By applying induction on edges e –
In case, if e = 0 then each vertex will be connected component which satisfies the clain
But, if e > 0, then pick ab as an edge
Let, G’’ be a graph which is obtained by removing this edge ab
Then, G’’ has at most one more component other than G
By using induction hypothesis,
G’’ must have at least one component as v – (e – 1)
So, it shows G has also at least v – (e – 1) = v – e components.
In this proof, two main approaches are used -
 Spanning tree including the fact that a tree of vertices v has exactly one edge e.
 Induction on the graph size by assuming that G has a connected graph of vertices and
edges, then on removal of edges, graph will split into two parts. By inductive hypothesis
both graphs have at least one edges and removal of any edge both graphs will be not
connected.
1