Ch. 2: Degrees
From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang)
58 flashcards · Mathematics · by lakesare
Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 1 courses
What is the degree degv\deg vdegv of a vertex vvv ?
The number of edges incident with vvv . Equivalently, the number of vertices adjacent to vvv . Written degGv\deg_G vdegGv when the graph needs naming.
What is the neighborhood N(v)N(v)N(v) of a vertex vvv ?
The set of neighbors of vvv , i.e. the vertices adjacent to vvv . So degv=∣N(v)∣\deg v = |N(v)|degv=∣N(v)∣ .
A vertex of degree 0 is an isolated vertex; a vertex of degree 1 is an end-vertex.
An end-vertex is also called a leaf.
What do δ(G)\delta(G)δ(G) and Δ(G)\Delta(G)Δ(G) denote?
δ(G)\delta(G)δ(G) = minimum degree, Δ(G)\Delta(G)Δ(G) = maximum degree among the vertices of GGG .
GGG has order nnn ( nnn vertices) and vvv is any vertex. Complete the chain: ?≤δ(G)≤degv≤Δ(G)≤ ?? \le \delta(G) \le \deg v \le \Delta(G) \le \; ??≤δ(G)≤degv≤Δ(G)≤?
0≤δ(G)≤degv≤Δ(G)≤n−1\boldsymbol{0} \le \delta(G) \le \deg v \le \Delta(G) \le \boldsymbol{n-1}0≤δ(G)≤degv≤Δ(G)≤n−1 A vertex can be adjacent to at most the n−1n-1n−1 other vertices.
The First Theorem of Graph Theory (Theorem 2.1) If GGG is a graph of size mmm ( mmm edges), then ∑v∈V(G)degv= ?\displaystyle\sum_{v \in V(G)} \deg v = \; ?v∈V(G)∑degv=?
2m\boldsymbol{2m}2m Each edge is counted twice, once at each of its two ends. Order 6, size 5: 2+1+2+4+1+0=10=2⋅52 + 1 + 2 + 4 + 1 + 0 = 10 = 2 \cdot 52+1+2+4+1+0=10=2⋅5 .
A graph has order 14 and size 27. Every vertex has degree 3, 4 or 5, and six vertices have degree 4. How many vertices have degree 3, and how many degree 5?
5 of degree 3, 3 of degree 5. With xxx vertices of degree 3: 3x+4⋅6+5(8−x)=2⋅273x + 4 \cdot 6 + 5(8 - x) = 2 \cdot 273x+4⋅6+5(8−x)=2⋅27 , so x=5x = 5x=5 .
A graph has order 14 and size 27, every vertex has degree 3, 4 or 5, and six vertices have degree 4. How many vertices have degree 3 and 5?Why can't you solve this by drawing one graph with these properties and counting?
A drawing doesn't show that every such graph gives the same answer. The equation from ∑degv=2m\sum \deg v = 2m∑degv=2m has a unique solution, so it does.
GGG is bipartite with partite sets UUU and WWW , and has size mmm . ∑u∈Udegu= ?\displaystyle\sum_{u \in U} \deg u = \; ?u∈U∑degu=?
m\boldsymbol{m}m , and likewise ∑w∈Wdegw=m\displaystyle\sum_{w \in W} \deg w = mw∈W∑degw=m . Every edge has exactly one end in UUU .
Corollary 2.3: every graph has an even number of odd vertices.
(An odd vertex has odd degree.) The degrees sum to 2m2m2m ; the even vertices contribute an even amount, so the odd degrees also sum to an even number. That needs an even count of odd numbers.
A graph GGG of order nnn has a vertex of degree n−1n - 1n−1 . What follows?
GGG is connected. That vertex www is adjacent to all others, so any two vertices x,yx, yx,y are joined by the path (x,w,y)(x, w, y)(x,w,y) .
Must a connected graph of order nnn have a vertex of degree n−1n - 1n−1 ?
No. The path PnP_nPn ( n≥4n \ge 4n≥4 ) is connected, yet no vertex has degree above 2.
Theorem 2.4 Let GGG be a graph of order nnn . If degu+degv≥n−1\deg u + \deg v \ge n - 1degu+degv≥n−1 for every two nonadjacent vertices uuu and vvv , then … ?
GGG is connected and diam(G)≤2\operatorname{diam}(G) \le 2diam(G)≤2 . diam(G)\operatorname{diam}(G)diam(G) is the greatest distance between two vertices of GGG .
In a graph of order nnn , why do two nonadjacent vertices x,yx, yx,y with degx+degy≥n−1\deg x + \deg y \ge n - 1degx+degy≥n−1 always have a common neighbor?
Pigeonhole: their ≥n−1\ge n - 1≥n−1 neighbors all lie among the n−2n - 2n−2 other vertices, so some vertex www is adjacent to both. Then (x,w,y)(x, w, y)(x,w,y) is a path of length 2. This is why degu+degv≥n−1\deg u + \deg v \ge n - 1degu+degv≥n−1 for all nonadjacent pairs makes a graph connected with diameter at most 2.
Corollary 2.5 A graph GGG of order nnn is connected if δ(G)≥ ?\delta(G) \ge \; ?δ(G)≥?
δ(G)≥n−12\boldsymbol{\delta(G) \ge \frac{n-1}{2}}δ(G)≥2n−1 Then any two nonadjacent u,vu, vu,v have degu+degv≥n−12+n−12=n−1\deg u + \deg v \ge \frac{n-1}{2} + \frac{n-1}{2} = n - 1degu+degv≥2n−1+2n−1=n−1 , and that degree-sum condition makes a graph connected.
A graph GGG of order nnn with δ(G)≥n−12\delta(G) \ge \frac{n-1}{2}δ(G)≥2n−1 is connected.By this, which minimum degree guarantees that a graph of order 8 is connected?
δ(G)≥4\delta(G) \ge 4δ(G)≥4 8−12=3.5\frac{8-1}{2} = 3.528−1=3.5 , and degrees are integers. For any even nnn : δ(G)≥n2\delta(G) \ge \frac{n}{2}δ(G)≥2n .
What does it mean that the bound in a theorem is sharp?
It can't be improved: with a weaker value, the theorem becomes false. e.g. in “ degu+degv≥n−1\deg u + \deg v \ge n - 1degu+degv≥n−1 for all nonadjacent u,vu, vu,v ⇒\Rightarrow⇒ GGG connected”, n−1n - 1n−1 can't be replaced by n−2n - 2n−2 .
If degu+degv≥n−1\deg u + \deg v \ge n - 1degu+degv≥n−1 for every two nonadjacent vertices u,vu, vu,v of a graph GGG of order nnn , then GGG is connected and diam(G)≤2\operatorname{diam}(G) \le 2diam(G)≤2 .Which graph shows that n−1n - 1n−1 here can't be lowered to n−2n - 2n−2 ?
2Kk2K_k2Kk , two disjoint copies of the complete graph KkK_kKk ( n=2kn = 2kn=2k ). Nonadjacent u,vu, vu,v lie in different copies, so degu+degv=2(k−1)=n−2\deg u + \deg v = 2(k - 1) = n - 2degu+degv=2(k−1)=n−2 , yet the graph is disconnected.
A graph of order nnn has kkk components. What is an upper bound on the order of its smallest component?
nk\boldsymbol{\frac{n}{k}}kn If every component had more than nk\frac{n}{k}kn vertices, the graph would have more than nnn .
Why does every disconnected graph GGG of order nnn have δ(G)≤n−22\delta(G) \le \frac{n-2}{2}δ(G)≤2n−2 ?
Some component has order n1≤n2n_1 \le \frac{n}{2}n1≤2n , so its vertices have degree at most n1−1≤n−22n_1 - 1 \le \frac{n-2}{2}n1−1≤2n−2 . This is the contrapositive of: δ(G)≥n−12\delta(G) \ge \frac{n-1}{2}δ(G)≥2n−1 makes GGG connected.
How is degv\deg vdegv counted in a multigraph (parallel edges allowed) or pseudograph (loops allowed too)?
The number of edges incident with vvv , where each loop at vvv counts 2. degu1=4, degu2=6, degu3=6, degu4=4\deg u_1 = 4, \ \deg u_2 = 6, \ \deg u_3 = 6, \ \deg u_4 = 4degu1=4, degu2=6, degu3=6, degu4=4
In a digraph, what are the outdegree odv\operatorname{od} vodv and indegree idv\operatorname{id} vidv of a vertex vvv ?
odv\operatorname{od} vodv = number of vertices vvv is adjacent to; idv\operatorname{id} vidv = number of vertices adjacent to vvv . Arcs leaving vvv and arcs entering vvv . odv1=idv1=1\operatorname{od} v_1 = \operatorname{id} v_1 = 1odv1=idv1=1 , odv2=2\ \operatorname{od} v_2 = 2 odv2=2 , idv2=1\operatorname{id} v_2 = 1idv2=1 , odv3=0\ \operatorname{od} v_3 = 0 odv3=0 , idv3=1\operatorname{id} v_3 = 1idv3=1
When is a graph regular, and when is it rrr -regular?
Regular: all vertices have the same degree. rrr -regular: every vertex has degree rrr . Regular means δ(G)=Δ(G)\delta(G) = \Delta(G)δ(G)=Δ(G) . All regular graphs of order 4 and 5.
Why is there no 3-regular graph of order 5?
It would have 5 odd vertices, but every graph has an even number of odd vertices. In general: no rrr -regular graph of order nnn exists when rrr and nnn are both odd.
A 3-regular graph is also called a cubic graph.
Examples: K4K_4K4 , K3,3K_{3,3}K3,3 , the 3-cube Q3Q_3Q3 and the Petersen graph.
Name this graph. What is its degree, and how many vertices and edges does it have?
The Petersen graph: 3-regular, 10 vertices, 15 edges. 15=10⋅3 / 215 = 10 \cdot 3 \,/\, 215=10⋅3/2 by the First Theorem of Graph Theory.
Theorem 2.6 Let 0≤r≤n−10 \le r \le n - 10≤r≤n−1 . An rrr -regular graph of order nnn exists if and only if … ?
At least one of rrr and nnn is even.
How is the Harary graph Hr,nH_{r,n}Hr,n built when r=2kr = 2kr=2k is even?
Place v1,…,vnv_1, \dots, v_nv1,…,vn in a cycle and join each viv_ivi to the kkk vertices before it and the kkk after it. H4,10H_{4,10}H4,10 : each vertex joined to 2 on each side.
How is the Harary graph Hr,nH_{r,n}Hr,n built when r=2k+1r = 2k + 1r=2k+1 is odd (so n=2ln = 2ln=2l is even)?
As for r=2kr = 2kr=2k , plus join each viv_ivi to the opposite vertex vi+lv_{i+l}vi+l . H5,10H_{5,10}H5,10 : 2 on each side, plus the vertex opposite.
What is a constructive proof?
A proof that actually builds an object with the required properties, rather than only showing that one exists. e.g. showing that an rrr -regular graph of order nnn exists (when rrr or nnn is even) by building the Harary graphs.
Theorem 2.7 For every graph GGG and every integer r≥Δ(G)r \ge \Delta(G)r≥Δ(G) , there exists … ?
An rrr -regular graph HHH containing GGG as an induced subgraph. Induced: HHH adds no edges between vertices of GGG . And r≥Δ(G)r \ge \Delta(G)r≥Δ(G) is needed, since an rrr -regular graph has no vertex of degree above rrr .
For every graph GGG and every integer r≥Δ(G)r \ge \Delta(G)r≥Δ(G) , there is an rrr -regular graph HHH containing GGG as an induced subgraph.How does the proof build the rrr -regular graph HHH from GGG ?
Take GGG and a copy G′G'G′ ; join each viv_ivi to its copy vi′v_i'vi′ whenever degvi<r\deg v_i < rdegvi<r . This raises the minimum degree by 1 and keeps GGG induced. Repeat r−δ(G)r - \delta(G)r−δ(G) times. Here r=4r = 4r=4 and δ(G)=2\delta(G) = 2δ(G)=2 : two rounds.
Who wrote the first book entirely devoted to graph theory, and when?
Dénes König, 1936. It contains the theorem that every graph is an induced subgraph of an rrr -regular graph for each r≥Δ(G)r \ge \Delta(G)r≥Δ(G) , stated for multigraphs.
GGG has order 6 and δ(G)=2\delta(G) = 2δ(G)=2 . Why must a 5-regular graph HHH containing GGG as an induced subgraph have order at least 10?
A degree-2 vertex of GGG needs 3 new neighbors outside GGG , so HHH has at least 9 vertices, and no 5-regular graph of order 9 exists (5 and 9 are both odd). A 5-regular HHH of order 10: four new vertices u,v,w,xu, v, w, xu,v,w,x .
What is a degree sequence of a graph?
The degrees of its vertices, listed in a sequence (in any order). e.g. 4,3,2,2,2,1,1,1,04, 3, 2, 2, 2, 1, 1, 1, 04,3,2,2,2,1,1,1,0
A finite sequence of nonnegative integers is called graphical if it is the degree sequence of some graph.
What are two quick reasons a sequence d1,…,dnd_1, \dots, d_nd1,…,dn can fail to be graphical?
An odd number of odd terms, or a term greater than n−1n - 1n−1 . Passing both checks isn't enough: 3,3,3,13, 3, 3, 13,3,3,1 fails anyway.
Why is 3,3,3,13, 3, 3, 13,3,3,1 not graphical?
The three vertices of degree 3 would be adjacent to all other vertices, so the fourth would have degree 3, not 1.
Havel–Hakimi theorem (Theorem 2.10) A non-increasing sequence s:d1,d2,…,dns: d_1, d_2, \dots, d_ns:d1,d2,…,dn ( n≥2n \ge 2n≥2 ) of nonnegative integers with d1≥1d_1 \ge 1d1≥1 is graphical if and only if … ?
Deleting d1d_1d1 and subtracting 1 from the next d1d_1d1 terms gives a graphical sequence: s1:d2−1, d3−1, …, dd1+1−1, dd1+2, …, dns_1: d_2 - 1, \ d_3 - 1, \ \dots, \ d_{d_1+1} - 1, \ d_{d_1+2}, \ \dots, \ d_ns1:d2−1, d3−1, …, dd1+1−1, dd1+2, …, dn
Havel–Hakimi: a non-increasing sequence s:d1,…,dns: d_1, \dots, d_ns:d1,…,dn with d1≥1d_1 \ge 1d1≥1 is graphical if and only if s1:d2−1,…,dd1+1−1,dd1+2,…,dns_1: d_2 - 1, \dots, d_{d_1+1} - 1, d_{d_1+2}, \dots, d_ns1:d2−1,…,dd1+1−1,dd1+2,…,dn is (delete d1d_1d1 , subtract 1 from the next d1d_1d1 terms).Why does a graphical s1s_1s1 make sss graphical?
Take a graph with degree sequence s1s_1s1 and add a new vertex adjacent to the d1d_1d1 vertices whose degrees were lowered.
Havel–Hakimi: a non-increasing sequence s:d1,…,dns: d_1, \dots, d_ns:d1,…,dn with d1≥1d_1 \ge 1d1≥1 is graphical if and only if s1:d2−1,…,dd1+1−1,dd1+2,…,dns_1: d_2 - 1, \dots, d_{d_1+1} - 1, d_{d_1+2}, \dots, d_ns1:d2−1,…,dd1+1−1,dd1+2,…,dn is (delete d1d_1d1 , subtract 1 from the next d1d_1d1 terms).The harder direction, sss graphical ⇒\Rightarrow⇒ s1s_1s1 graphical: what is the key idea of the proof?
Among graphs with degree sequence sss , take one where the neighbors of v1v_1v1 have the largest possible degree sum. If v1v_1v1 were adjacent to some vsv_svs but not to a higher-degree vrv_rvr , an edge swap would raise that sum, a contradiction. So v1v_1v1 is adjacent to the d1d_1d1 highest-degree vertices, and deleting it leaves s1s_1s1 . The swap: remove v1vsv_1v_sv1vs and vrvtv_rv_tvrvt , add v1vrv_1v_rv1vr and vsvtv_sv_tvsvt (dashed = no edge).
Is 5,4,3,3,2,2,2,1,1,15, 4, 3, 3, 2, 2, 2, 1, 1, 15,4,3,3,2,2,2,1,1,1 graphical?
Yes. →3,2,2,2,1,1,1,1,1 → 1,1,1,1,1,1,1,1\to 3, 2, 2, 2, 1, 1, 1, 1, 1 \;\to\; 1, 1, 1, 1, 1, 1, 1, 1→3,2,2,2,1,1,1,1,1→1,1,1,1,1,1,1,1 , the degree sequence of 4K24K_24K2 .
Havel–Hakimi step: delete the largest term d1d_1d1 and subtract 1 from the next d1d_1d1 terms. Repeat until the sequence is obviously graphical (or not).The steps ended with a sequence you recognise as a graph's. How do you build a graph for the original sequence?
Work backwards: at each step, add a new vertex joined to the vertices whose degrees were reduced. For 5,4,3,3,2,2,2,1,1,15, 4, 3, 3, 2, 2, 2, 1, 1, 15,4,3,3,2,2,2,1,1,1 : from 4K24K_24K2 to G1G_1G1 to GGG .
Is 7,7,4,3,3,3,2,17, 7, 4, 3, 3, 3, 2, 17,7,4,3,3,3,2,1 graphical?
No. →6,3,2,2,2,1,0 → 2,1,1,1,0,−1\to 6, 3, 2, 2, 2, 1, 0 \;\to\; 2, 1, 1, 1, 0, -1→6,3,2,2,2,1,0→2,1,1,1,0,−1 : a negative term.Faster: two vertices of degree 7 in a graph of order 8 are adjacent to every other vertex, so no vertex can have degree 1.
What is the adjacency matrix A=[aij]A = [a_{ij}]A=[aij] of a graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn ?
The n×nn \times nn×n matrix with aij=1a_{ij} = 1aij=1 if vivjv_iv_jvivj is an edge, and 0 otherwise.
What is the incidence matrix B=[bij]B = [b_{ij}]B=[bij] of a graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn and edges e1,…,eme_1, \dots, e_me1,…,em ?
The n×mn \times mn×m matrix with bij=1b_{ij} = 1bij=1 if viv_ivi is incident with eje_jej , and 0 otherwise.
In the adjacency matrix AAA and the incidence matrix BBB of a graph: what does row iii add up to, and what does each column of BBB add up to?
Row iii of AAA or of BBB : degvi\deg v_idegvi . Each column of BBB : 2. Every edge has two ends. Also, AAA is symmetric with zeros on the diagonal.
Theorem 2.13. AAA is the adjacency matrix of a graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn . What does the entry aij(k)a^{(k)}_{ij}aij(k) in row iii , column jjj of AkA^kAk count?
The number of viv_ivi – vjv_jvj walks of length kkk .
A=[aij]A = [a_{ij}]A=[aij] is the adjacency matrix of a graph, and (by induction) the entries ait(k)a^{(k)}_{it}ait(k) of AkA^kAk count the viv_ivi – vtv_tvt walks of length kkk .Why does aij(k+1)=∑tait(k) atja^{(k+1)}_{ij} = \sum_t a^{(k)}_{it} \, a_{tj}aij(k+1)=∑tait(k)atj count the viv_ivi – vjv_jvj walks of length k+1k + 1k+1 ?
Every such walk is a walk of length kkk from viv_ivi to some neighbor vtv_tvt of vjv_jvj , followed by the edge vtvjv_tv_jvtvj . atj=1a_{tj} = 1atj=1 exactly when vtv_tvt is adjacent to vjv_jvj . This is the induction step showing that aij(k)a^{(k)}_{ij}aij(k) counts the viv_ivi – vjv_jvj walks of length kkk .
AAA is the adjacency matrix of a graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn . What do the diagonal entries aii(2)a^{(2)}_{ii}aii(2) and aii(3)a^{(3)}_{ii}aii(3) of A2A^2A2 and A3A^3A3 count?
aii(2)=a^{(2)}_{ii} = aii(2)= degvi\deg v_idegvi ; aii(3)=\ a^{(3)}_{ii} = aii(3)= twice the number of triangles containing viv_ivi Each triangle can be walked around in 2 directions.
When is a graph irregular?
It has order at least 2 and every two vertices have different degrees.
What does the Party Theorem say?
At any party, two people have the same number of friends present. In graph terms: no nontrivial graph is irregular, i.e. every graph of order at least 2 has two vertices of the same degree.
Why is no nontrivial graph irregular?
nnn different degrees from 0,1,…,n−10, 1, \dots, n - 10,1,…,n−1 means both degree 0 and degree n−1n - 1n−1 occur, but then the degree- (n−1)(n-1)(n−1) vertex is adjacent to the degree-0 vertex. Contradiction.
For a graph FFF , what is the FFF -degree FdegvF\deg vFdegv of a vertex vvv in a graph GGG ?
The number of copies of FFF in GGG that contain vvv (subgraphs with the structure of FFF , induced or not). For F=K2F = K_2F=K2 it is the ordinary degree. F=K3F = K_3F=K3 : each vertex labelled with its number of triangles.
Theorem 2.15 Let FFF be a graph of order k≥2k \ge 2k≥2 . If GGG contains mmm copies of FFF , then ∑v∈V(G)Fdegv= ?\displaystyle\sum_{v \in V(G)} F\deg v = \; ?v∈V(G)∑Fdegv=?
km\boldsymbol{km}km Each copy is counted once for each of its kkk vertices. With F=K2F = K_2F=K2 this is the First Theorem of Graph Theory.
Conjecture 2.17. For which nontrivial connected graphs FFF does an FFF -irregular graph exist (all vertices with different FFF -degrees)?
Every FFF except K2K_2K2 . K2K_2K2 fails by the Party Theorem. For F=P3F = P_3F=P3 , an example:
What is the underlying graph of a multigraph MMM ?
The graph obtained by replacing each set of parallel edges by a single edge. A multigraph can also be drawn as a weighted graph: each edge labelled with its number of parallel edges.
Theorem 2.18. Which connected graphs of order at least 2 are the underlying graph of some irregular multigraph?
Every one except K2K_2K2 . e.g. K3K_3K3 with edge weights 1, 2, 3 has degrees 3, 4 and 5.