Page 1 :
Unit 5, 2. Basic Terminology

Page 2 :
Basic terminology, A graph G is a pair of sets (V, E) where V is nonempty, and E is a, (possibly empty) set of unordered pairs of elements of V., The elements of V are called the vertices of G and the elements of E, are called the edges of G., Sometimes we will write V(G) for the vertices of G and E(G) for the, edges of G.

Page 3 :
The two vertices u and v are end, vertices of the edge (u, v)., Edges are adjacent if they share a, common end vertex. Two vertices u, and v are adjacent if they are, connected by an edge, in other words,, (u, v) is an edge., Edges that have the same end, vertices are parallel.,  An edge with same initial and, terminal vertex of the form (v, v) is a, loop.

Page 4 :
Degree of a Vertex, The degree of the vertex v in Graph, G, written as 𝑑𝐺 (v), is the number, of edges with v as an end vertex. By, convention, we count a loop twice, and parallel edges contribute, separately.,  A pendant vertex is a vertex whose, degree is 1., An edge that has a pendant vertex, as an end vertex is a pendant edge.,  An isolated vertex is a vertex, whose degree is 0.

Page 5 :
Let v1, v2,..., vp be the vertices of a graph G, and let d1, d2,..., dp be the, degrees of the vertices, respectively. Let q be the number of edges of G., Then, d1 + d2 + ... + dp = 2q., Theorem 1.1.1 could be stated as follows. For Every graph G,, 𝑑𝐺 (𝑣𝑖 ) = 2𝑞, 𝑣𝑖 ∈𝑉(𝐺), , Proof: In every graph, every edge contributes twice to the degree of, vertices, we have the above result., Is there a graph with seven vertices, each of which has degree 5?

Page 8 :
Theorem: Every graph has atlest two vertices of same degree., Proof:Suppose every vertices has a different degree, then the degrees, of the vertices of G must be 0, 1, 2, 3,…p-1. However, a vertex of degree, n-1 must be adjacent to all the other vertices of G; and consequently, there cannot be a vertex of degree 0 in G: This contradiction shows that, the degrees of the vertices of G cannot all be distinct, and hence at, least two of them should have the same degree.

Page 9 :
Degree sequence of a graph, The non increasing(nondecreasing) sequence of degrees of a graph is, called degree sequence of a graph.

Page 10 :
A sequence of non-negative integers is called graphic if there exists a, graph whose degree sequence is precisely that sequence.

Page 11 :
Havel, Hakimi theorem, Theorem 1.1.2. (Havel, Hakimi) Consider the following two sequences, and assume sequence (1) is in descending order., (1) s, t1, t2,..., ts, d1,..., dn, (2) t1−1, t2−1,..., ts−1, d1,..., dn, Then sequence (1) is graphic if and only if sequence (2) is graphic., Proof. First assume that sequence (2) is graphic. Then there is a graph, G2 with degree sequence equal to sequence (2). We construct G1from, G2, by adding a vertex and connecting it to the vertices whose degrees, are t1−1, t2−1,..., ts−1. Then G1is a graph with degree sequence equal to, sequence (1), hence sequence (1) is graphic.

Page 12 :
Now we suppose that sequence (1) is graphic. Then there is a graph H,, with degree sequence (1)., Let the vertex S have degree s, Ti have degree ti, Di have degree di. If S is, adjacent to T1, T2,..., Ts, then we simply remove this vertex and the, edges incident with it, thus obtaining a graph with degree sequence, equal to sequence (2)., However, this may not be the case. Suppose that for some i with 1 ≤ i ≤, s vertex S is not adjacent to vertex Ti. Then vertex S is adjacent to some, vertex Dj with j ≥ 1., Since the sequence is arranged in descending order, ti ≥ dj. If ti = dj, we, simply exchange Ti and Dj.

Page 13 :
If ti > dj, then Ti has more neighbors than Dj has, so there is a vertex W., such that Tiis adjacent to W and Djis not adjacent to W. We do not, know whether W is one of the T-vertices or one of the D-vertices, but it, does not matter., In this case we remove the edges SDj and TiW and add the edges STi and, DjW to obtain the graph H2, still having the degree sequence (1)., If S is now adjacent to T1, T2,..., Ts, as before we remove S to obtain a, graph with sequence (2). If not we repeat the above procedure. Since, this is a finite graph, for some m, Hm is the graph we seek. Thus, sequence (2) is graphic.

Page 15 :
We now use the procedure to determine whether sequence is, graphic., 66664330, 5553220, 442110, 31000, Since there is no graph with one vertex of degree 3, one vertex of, degree 1 and three vertices of degree 0, we see that the last sequence, is not graphic, hence neither is first sequence.

Page 16 :
Which of the following sequences are graphic?, a. 5 5 4 4 3 2 2 1 1, b. 6 5 4 3 2 2 2 2, c. 4 4 4 4 3 3, d. 7 6 5 4 4 3 2 1

Page 17 :
Is either of the following sequences graphic?, a) (6,6,5,5,2,2,2,2), b) (6,6,5,5,3,3,3,3)., Draw a graph with degree sequence, a) (4, 3, 2, 2, 1), b) (4, 3, 3, 3, 1)., 1.1.10.