Definition (Degree).
The degree of a vertex \(v\) in a graph \(G\) (not necessarily simple) is denoted by \(\operatorname{d}(v)\) or \(\operatorname{deg}(v)\)
and is defined to be the number of edges incident with \(v\) where a loop at \(v\) contributes \(2\) to \(\operatorname{d}(v)\).
Example.
In the preceding graph \(G\),
\[\operatorname{d}(f)=0,\;\operatorname{d}(c)=1,\;\operatorname{d}(d)=3,\;\operatorname{d}(a)=2,\;\operatorname{d}(b)=4.\]
Theorem (The handshaking lemma).
The sum of degrees of a graph \(G=(V,E)\) is twice the number of its edges, i.e.,
\[\sum_{v\in V} \operatorname{d}(v)=2|E|.\]
A loop at a vertex \(v\) contributes two to \(\operatorname{d}(v)\). A non-loop edge \(e=\{u,v\}\) contributes one to each of
\(\operatorname{d}(u)\) and \(\operatorname{d}(v)\). Thus each edge contributes two to the degree-sum which implies
\[\sum_{v\in V} \operatorname{d}(v)=2|E|.\]
Corollary.
The number of vertices of odd degree in a graph is even.
Consider a graph \(G=(V,E)\). Suppose \(V_o\) and \(V_e\) are the sets of vertices of \(G\) of odd degree and even degree respectively. Then
\[\sum_{v\in V} \operatorname{d}(v)=\sum_{v\in V_o} \operatorname{d}(v)+\sum_{v\in V_e} \operatorname{d}(v).\]
Since \(\sum_{v\in V} \operatorname{d}(v)=2|E|\) by the handshaking lemma,
\[\sum_{v\in V_o} \operatorname{d}(v)+\sum_{v\in V_e} \operatorname{d}(v)=2|E|
\implies \sum_{v\in V_o} \operatorname{d}(v)=2|E|-\sum_{v\in V_e} \operatorname{d}(v).\]
Since \(\operatorname{d}(v)\) is even for all \(v\in V_e\), \(\sum_{v\in V_e} \operatorname{d}(v)\) is even and consequently so is
\[\sum_{v\in V_o} \operatorname{d}(v)=2|E|-\sum_{v\in V_e} \operatorname{d}(v).\]
Since \(\sum_{v\in V_o} \operatorname{d}(v)\) is even and \(\operatorname{d}(v)\) is odd for all \(v\in V_o\), \(|V_o|\) is even.
Example.
In the preceding graph \(G\),
\[\sum_{v\in V} \operatorname{d}(v)
=\operatorname{d}(f)+\operatorname{d}(c)+\operatorname{d}(d)+\operatorname{d}(a)+\operatorname{d}(b)=0+1+3+2+4=10\]
which is twice the number of edges of \(G\). Also note that \(G\) has two vertices of odd degree, viz, \(c\) and \(d\).
Definition (Degree sequence).
The degree sequence of a graph \(G\) is the nonincreasing sequence of vertex degrees of \(G\).
Example.
The degree sequence of the preceding graph \(G\) is \((4,3,2,1,0)\).
Remark.
If \((d_1,d_2,\ldots,d_n)\) is the degree sequence of a graph \(G=(V,E)\), then \(d_1\geq d_2\geq \cdots \geq d_n\), \(|V|=n\), and
\[ |E|=\frac{d_1+d_2+ \cdots +d_n}{2}.\]
Example.
Is there any graph with the degree sequence \((4,3,2,0)\)?
If possible, draw a graph with the degree sequence \((4,2,2,0)\).
Theorem (Erdös-Gallai theorem, 1960).
\((d_1,d_2,\ldots,d_n)\) is the degree sequence of a simple graph if and only \(\sum_{i=1}^n d_i\) is even and for all \(k=1,2,\ldots,n\),
\[\sum_{i=1}^k d_i \leq k(k-1)+\sum_{i=k+1}^n \min\{d_i,k\}.\]
Definition (Regular graph).
A graph \(G\) is \(k\)-regular if \(\operatorname{d}(v)=k\) for all \(v\in V(G)\).
Example.
\(K_n\), the complete graph on \(n\) vertices, is a simple graph in which any two edges are adjacent. Note that \(K_n\) is
\((n-1)\)-regular and \(|E(K_n)|=\binom{n}{2}=\frac{n^2-n}{2}\).
\(C_n\), the cycle on \(n\geq 3\) vertices, is a simple graph whose vertices can be labeled as \(1,2,\ldots,n\) so that
\(E(C_n)=\{\{1,2\},\;\{2,3\},\ldots,\{n-1,n\},\;\{n,1\}\}\). Note that \(C_n\) is \(2\)-regular and \(|E(C_n)|=n\).
\(P_n\), the path on \(n\geq 3\) vertices, is a simple graph which can be obtained from some \(C_n\) by deleting one edge.
Note that \(P_2=K_2\) and \(P_1=K_1\) which are the only regular paths.
\(W_n\), the wheel on \(n\geq 4\) vertices, is a simple graph obtained by joining a vertex to all the vertices of \(C_{n-1}\).
Note that \(W_4\) is \(3\)-regular but \(W_n\) is not regular for all \(n\geq 5\).
Petersen graph is a famous graph on \(10\) vertices which is \(3\)-regular.
Problem.
The complement of a simple graph \(G\), denoted by \(\overline{G}\) or \(G^c\), is the simple graph with the same vertices as \(G\)
in which \(\{i,j\}\) is an edge if and only if \(\{i,j\}\) is not an edge in \(G\). Suppose \((d_1,d_2,\ldots,d_n)\) is the degree sequence of
a simple graph \(G\).
Find the degree sequence of \(\overline{G}\).
Use the degree sequence of \(\overline{G}\), to write the number of edges of \(\overline{G}\) in terms of \(n\) and \(m\),
the number of edges of \(G\).
