Definition and Notation A simple graph is a graph that does not have any loopsor parallel edges. In a simple graph, an edge with endpoints v and w isdenoted{v,w}.
Example 10.1.8 A Simple Graph Draw all simple graphs with the four vertices {u,v,w,x} and two edges, one of which is{u,v}.
Definition A graph H issaid to be a subgraph of a graph G if, and only if, every vertex in H is also a vertex in G, ever y edge in H is also an e dge in G, an d every edge in H has the same en dpoints as it has in G.
Example 10.1.11 Subgraphs List all subgraphs of the graph G with vertexset{v1,v2}and edge set{e1,e2,e3}, where the endpoints of e1 are v1 and v2, the endpoints of e2 are v1 and v2, and e3 is a loop at v1.
The Concept of Degree The degree of a vertex is the number of endsegments of edges that “sticko ut of” the vertex. We will show that the sum of the degrees of all the vertices in a graph is twice the number of edges of the graph.
10.1 Graphs: Definitions and Basic Properties 635
Definition.Let G be a graph and v a verte x of G. Thedegree of v, denoted deg(v), equals the number of edges that are incident on v, with an edge that is a loop counted twice. The total degree of G is the sum of the degrees of all the vertices of G.
Since an e dge that is a loop isc ounted twice, the degree of a vertexcan be obtained from the drawing of a graph byc ounting how many endsegments of edges are incident on the vertex. This is illustrated below.
Consider the directedgraph shown inFigure 10.3.1. This graph can be represented bythe matrix A= (aij) for which aij =the number of arrows from vi to vj, for all i =1,2,3 and j =1,2,3. Thus a11 =1 be cause there is one arrow from v1 to v1,a12 =0 be cause there is no arrow from v1 to v2,a23 =2 be cause there are two arrows from v2 to v3, an d so forth. A iscalled the adjacency matrix of the directed graph. For convenient reference, the rows andcolumns of A are often labeled with the vertices of the graph G.
Definition
LetG beadirectedgraphwithorderedverticesv1,v2,...,vn.Theadjacencymatrix of G is the n × n matrix A= (aij) over the set of nonnegative integers such that aij =the number of arrows from vi to vj for all i, j =1,2,...,n.
.
10.3 Matrix Representations of Graphs 663
Note that nonzero entries along the main diagonal of an adjacency matrix indicate the presence of loops, and entries larger than 1 correspond to parallel edges. Moreover, if the vertices of a directed graph are reordered, then the entries in the rows andcolumns of the corresponding adjacency matrix are moved around.
Example 10.3.2 The Adjacency Matrix of a Graph The two directed graphsshown below differ only in the ordering of their vertices.
Find their adjacency matrices.