We now make a few formal definitions, and set up some notation. A graph G consists of a finite set V or V(G) of objects called vertices, together with a collection E(G)  of pairs of vertices that are called edges. (This is consistent with the use of “vertex”  and “edge” earlier.) The two vertices belonging to an edge are called its endpoints;  we say they are adjacent, and say the edge joins them. An edge with endpoints

Fig. 1.1 Three representations of the same graph

X and Y will be written as {X,Y}, or simply XY when no confusion can arise.

Adjacent vertices are called neighbors. We write x ∼ y to mean that vertices x and y are adjacent.

In the diagram representing a graph, an edge XY is shown as a line from X to Y. This is usually drawn as a straight line segment, but not always; the only important thing is that it joins the correct points. Moreover, the position of the points is not fixed. For these two reasons, one graph can give rise to several drawings that look quite dissimilar. For example, the three diagrams in Fig. 1.1 all represent the same graph. Although the two diagonal lines cross in the first picture, their point of intersection does not represent a vertex of the graph.

It is not clear whether or not the definition of a graph allows for two edges with the same endpoints. Some authors interpret “collection of pairs” to mean that repeated pairs are permitted, while others do not. However, there are some situations where we wish to represent several different links between two vertices. The road system modeled in Fig.1.1bin(Representing Roads: The Königsberg Bridges) is an example. The lines representing the two roads from B to C in that figure will be called multiple edges. We say there is a multiple edge of multiplicity 2 joining B to C. If multiple edges are present, the diagram is called a multigraph; if we want to emphasize the fact that multiple edges are not allowed, we use the term simple graph. We might also want an edge that goes from a vertex back to the same vertex, representing for example a crescent in a road system, this would be called a loop; the usual interpretation is that loops are not allowed, unless the term “looped graph” or “looped multigraph” is used.

Another question is, can you have a graph with no vertices at all? Some authors say “yes,” and admit the concept of a graph with no vertices or edges at all. But we shall always require that a graph have at least one vertex. So the smallest possible graph will have one vertex and no edges. We shall call it the null graph orempty graph.

We shall define a walk (A,B,C,...,Y,Z) to be a sequence of vertices (A,B,C, ...,Y,Z) such that AB,BC,...,Y Z are all edges. For example, the diagram of Fig. 6.1a represents a graph that contains a walk (A,B,C,D), because each of AB,  B,C and C,D is an edge of the graph. Similarly, there is a walk (A,C,D). However,  there is no walk (A,B,D), because there is no edge BD. In terms of the model as a road system, a walk is a sequence of roads that you could traverse in order. A circuit (or closed walk) is a walk that finishes at its starting point; Fig. 1.1ain(Representing Roads: The Königsberg Bridges)  contains a circuit (A,B,C,A). A walk is called simple if no edge is repeated; in graph (a),  (A,B,C,A,B) is a walk, but edge AB is repeated, so it is not simple. The length of a walk is the number of edges that it contains.

The degree (or valency) of a vertex is the number of edges with that vertex as an endpoint; we’ll write d(x) for the degree of a vertex x. A vertex whose degree is odd is called an odd vertex; others are even. (For completeness, we say that each loop adds 2 to the degree of the vertex.)

Sample Problem 1.1 Find the degrees of all the vertices in these graphs:

Given a graph with e edges, suppose you wrote down a list of the edges, once each. Then replace each edge by its pair of vertices. For example, if y₁ is an edge with endpoints x₄ and x₇, you might make erase the entry y₁ and instead write downx₄ and x₇. Then a vertex x will appear precisely d(x) times in the list, so the total number of entries equals the sum of the degrees of the vertices. On the other hand,  each edge appeared once in the original list, so each edge gives rise to two entries in the revised list. So there are 2e entries in the new list—an even number. Putting it another way, the number of edges in a graph is precisely half the sum of all the degrees.

If you add together an odd number of odd integers, together with any number of even numbers, you get an odd number. This can’t have happened in the revised list.

So the number of odd integers in the revised list is even. That is, in any graph, the number of odd vertices is even.

So far, nothing we have said implies that a graph must be all one piece. Figure 1.1=showed three graphs, but you could also consider them as one graph, made up of three separate parts. In that case, we would say the graph is disconnected. For example, Fig. 1.1might represent the major highways on three islands that are not connected by bridges.

If the graph is all one piece, it is called a connected graph. The connected parts of a disconnected graph are called its components.

In a number of cases, we consider graphs in which every pair of vertices is joined by an edge. In that case, we say the graph is complete. Complete graphs are particularly important when a number, such as a distance or a cost, is associated witheach edge. A complete graph with n vertices is denoted Kn; for example, Fig. 1.1 shows three different ways to draw the graph K₄. Clearly K₁, the null graph, is a  (rather trivial) complete graph.

An alternative way of representing a graph is its incidence array. This is an array in which the rows and columns both represent the vertices of the graph, in the same order. A 1 in position (i, j) means that there is an edge joining the vertices, while a 0 indicates no edge. In the case of a multigraph, some people replace the 1 by the number of edges, while others simply use the array to show which vertices are connected. In cases where only the structure is important, the incidence matrix, with the names of the vertices not shown, contains all the information needed.

If we reorder the list of vertices, this will produce a reordering of the rows and columns of the incidence array and of the incidence matrix. Two incidence matrices are called equivalent when one can be obtained from the other by performing a permutation on the rows and the same permutation on the columns.