162 GRAPH THEORY [CHAP. 8
Although it is clear that only connected graphs can be Hamiltonian, there is no simple criterion to tell us
whether or not a graph is Hamiltonian as there is for Eulerian graphs. We do have the following sufficient condition
which is due to G. A. Dirac.
Theorem 8.5: LetGbe a connected graph withnvertices. ThenGis Hamiltonian ifn≥3 andn≤deg(v)for
each vertexvinG.
8.6Labeled and Weighted Graphs
A graphGis called alabeled graphif its edges and/or vertices are assigned data of one kind or another. In
particular,Gis called aweighted graphif each edgeeofGis assigned a nonnegative numberw(e)calledthe
weightorlengthofv. Figure 8-12 shows a weighted graph where the weight of each edge is given in the obvious
way. Theweight(orlength) of a path in such a weighted graphGis defined to be the sum of the weights of the
edges in the path. One important problem in graph theory is to find ashortest path, that is, a path of minimum
weight (length), between any two given vertices. The length of a shortest path betweenPandQin Fig. 8-12 is
14; one such path is
(P , A 1 ,A 2 ,A 5 ,A 3 ,A 6 ,Q)
The reader can try to find another shortest path.
Fig. 8-128.7Complete, Regular, and Bipartite Graphs
There are many different types of graphs.This section considers three of them: complete, regular, and bipartite
graphs.
Complete Graphs
AgraphGis said to becompleteif every vertex inGis connected to every other vertex inG. Thus a complete
graphGmust be connected. The complete graph withnvertices is denoted byKn. Figure 8-13 shows the graphs
K 1 throughK 6.
Regular Graphs
A graphGisregular of degree kork-regularif every vertex has degreek. In other words, a graph is regular
if every vertex has the same degree.
The connected regular graphs of degrees 0, 1, or 2 are easily described. The connected 0-regular graph is
the trivial graph with one vertex and no edges. The connected 1-regular graph is the graph with two vertices and
one edge connecting them. The connected 2-regular graph withnvertices is the graph which consists of a single
n-cycle. See Fig. 8-14.
The 3-regular graphs must have an even number of vertices since the sum of the degrees of the vertices is
an even number (Theorem 8.1). Figure 8-15 shows two connected 3-regular graphs with six vertices. In general,
regular graphs can be quite complicated. For example, there are nineteen 3-regular graphs with ten vertices. We
note that the complete graph withnverticesKnis regular of degreen−1.