The distance between two nodes is the shortest distance between the two nodes.
A graph that starts and ends in the same node is called a cycle or a closed circuit.
A simple path trespasses every node only once.
Let n be a node in a graph or multigraph G. The degree or valence of v is the number of arcs having an endpoint in v.
This number can be written as deg(v).
The handshaking lemma: At a large party where everybody shakes hand but not with everybody the number of persons having shaken hand an odd number of times is even.
a graph where it is allowed to pass a node several times is called a
a complete graph is a graph without loops and where every pair of nodes are connected with an arc.
Ex. Let G be a loop-free graph with n nodes, such that G has 175 arcs and its complement has 56 arcs. Determine n.
Solution: The totla number of arcs in G and its complement equals the number of arcs in the complete graph Kn.
Therefore 175 + 56 = n(n-2)/2 or ”n over 2” &imp; 231 = n(n-1)/2 &imp; n=22 ∧ n=-21.