The structure of your proof would be:
    Have a base case on any graph with a single edge.
       There would be two sub-cases; 
           the edge from node A to itself 
           the edge from node A to node B  

    The inductive hypothesis/step.
       The inductive hypothesis would be for a graph with k edges.
       The inductive step would be for a graph with k+1 edges.