What is the best way to carry out a proof in graph theory?

Answer 1

There is no single best way. Sometimes you use counting principles, sometimes proof by induction, sometimes proof by contradiction, and sometimes you build a new proof on the scaffolding of previous proofs.

In general, it is a very good idea to draw diagrams. A small-sized example often gives insight into the behaviour of a larger structure. Read some good texts and study the methods of prof as well as the actual theorems.