112 CHAPTER 2 Discrete Mathematics
Definition. The degreeof a vertexv in a graph is the number of
edges on this vertex. A loop on a vertex is counted twice in computing
the degree of a vertex.
Notice that if we are given the adjacency matrix, then the sum of
the elements of thei-th row is the degree of the vertexi.
Theorem. LetGbe a finite graph with adjacency matrixA. Then the
number of walks of length 2 from vertexvito vertexvjis the(i,j)entry
ofA^2. More generally, the number of walks of lengthk from vertexvi
to vertexvj is the(i,j)entry ofAk.
A moment’s thought is also enough to be convinced of the following
theorem:
Theorem. (Euler’s Theorem)LetGbe a graph.
(i) If the graph has any vertices ofodddegree, thenGcannot contain
an Eulerian circuit.(ii) If the graph has more than two vertices of odd degree, then G
cannot contain an Eulerian trail.As a result of Euler’s theorem, we see that the bridges of K ̈onigsberg
problem has no solution!
Example 1. The picture to the right
depicts a graphGbelow with exactly two
vertices of odd degree, one at vertex A
and one at vertexB. The reader should
have no difficulty in concluding that G
has no Eulerian circuits but does have an
Eulerian trail fromAtoB(or fromBto
A).
Notice that if we add the degrees of all the vertices in a graph, then
every edge get counted twice; this already proves the following.