Handshaking lemma in graph theory basically says that The degree sum is equal to twice the number of edges.
The doubt I have is, does this condition enough to prove the existence of the graph. That is if the degree sum is even then a graph exists with that corresponding degree sequence.
This may not be true when the simple graphs are considered. But what if we allow loops and multiple edges
$\endgroup$2 Answers
$\begingroup$Sure, per David Eppstein's contribution to Wikipedia:
$\endgroup$ 3 $\begingroup$The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops.
Chris Culter has your answer when (multiple) loops are allowed.
For simple graphs, you can use the Havel–Hakimi algorithm to establish whether a given set of vertex degree values - a degree sequence - corresponds to a graph.
The process is that you sort the degree sequence descending then generate a new sequence by removing a highest-degree node of degree $d$ and subtract one off each of the following $d$ degree values, to produce a new shorter sequence.
The process can be applied repeatedly until you reach a sequence that is trivial to recognize as possible or impossible. (In principle, for a graphical sequence - one that corresponds to a realizable graph - this process can be continued to finish with all zeroes).
Working a sample degree sequence:
$\begin{array}{c} &3&3&3&3&2\\ &&2&2&2&2\\ &&&1&1&2\\ \text{re-sort}&&&2&1&1\\ &&&&0&0&\checkmark \\ \end{array}$
$\endgroup$ 1
