The fact that each edge links exactly two nodes, no more and no less, imposes some conditions on ugraphs. Therefore a visit to every edge is a visit to each node in the ugraph twice. This fact supports the following two theorems.
Theorem 1.1a There are exactly (N-1)/2 edges in a complete ugraph with N nodes.
The following is true for every ugraph, complete or not.
Theorem 1.1b In a ugraph the sum of the degrees of all the nodes iequals twice the number of edges.
Theorem 1.1c In a ugraph the number of nodes of odd degree must be even.
For this folder chapter 01:
Return to top of main text
/
section 1.1