See section 4.4 to review some basic terminology about graphs.
A graph $G$ consists of a pair $(V,E)$, where $V$ is the set of vertices and $E$ the set of edges. We write $V(G)$ for the vertices of $G$ and $E(G)$ for the edges of $G$ when necessary to avoid ambiguity, as when more than one graph is under discussion.
If no two edges have the same endpoints we say there are no multiple edges, and if no edge has a single vertex as both endpoints we say there are no loops. A graph with no loops and no multiple edges is a simple graph. A graph with no loops, but possibly with multiple edges is a multigraph. The condensation of a multigraph is the simple graph formed by eliminating multiple edges, that is, removing all but one of the edges with the same endpoints. To form the condensation of a graph, all loops are also removed. We sometimes refer to a graph as a general graph to emphasize that the graph may have loops or multiple edges.
The edges of a simple graph can be represented as a set of two element sets; for example, $$(\{v_1,\ldots,v_7\},\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_3,v_5\}, \{v_4,v_5\},\{v_5,v_6\},\{v_6,v_7\}\}) $$ is a graph that can be pictured as in figure 5.1.1. This graph is also a connected graph: each pair of vertices $v$, $w$ is connected by a sequence of vertices and edges, $v=v_1,e_1,v_2,e_2,\ldots,v_k=w$, where $v_i$ and $v_{i+1}$ are the endpoints of edge $e_{i}$. The graphs shown in figure 4.4.2 are connected, but the figure could be interpreted as a single graph that is not connected.
A graph $G=(V,E)$ that is not simple can be represented by using multisets: a loop is a multiset $\{v,v\}=\{2\cdot v\}$ and multiple edges are represented by making $E$ a multiset. The condensation of a multigraph may be formed by interpreting the multiset $E$ as a set.
A general graph that is not connected, has loops, and has multiple edges is shown in figure 5.1.2. The condensation of this graph is shown in figure 5.1.3.
The degree of a a vertex $v$, $\d(v)$, is the number of times it appears as an endpoint of an edge. If there are no loops, this is the same as the number of edges incident with $v$, but if $v$ is both endpoints of an edge, namely, of a loop, then this contributes 2 to the degree of $v$. The degree sequence of a graph is a list of its degrees; the order does not matter, but usually we list the degrees in increasing or decreasing order. The degree sequence of the graph in figure 5.1.2, listed clockwise starting at the upper left, is $0,4,2,3,2,8,2,4,3,2,2$. We typically denote the degrees of the vertices of a graph by $d_i$, $i=1,2,\ldots,n$, where $n$ is the number of vertices. Depending on context, the subscript $i$ may match the subscript on a vertex, so that $d_i$ is the degree of $v_i$, or the subscript may indicate the position of $d_i$ in an increasing or decreasing list of the degrees; for example, we may state that the degree sequence is $d_1\le d_2\le \cdots\le d_n$.
Our first result, simple but useful, concerns the degree sequence.
Theorem 5.1.1 In any graph, the sum of the degree sequence is equal to twice the number of edges, that is, $$\sum_{i=1}^n d_i = 2|E|.$$
Proof. Let $d_i$ be the degree of $v_i$. The degree $d_i$ counts the number of times $v_i$ appears as an endpoint of an edge. Since each edge has two endpoints, the sum $\sum_{i=1}^n d_i$ counts each edge twice. $\qed$
An easy consequence of this theorem:
Corollary 5.1.2 The number of odd numbers in a degree sequence is even. $\qed$
An interesting question immediately arises: given a finite sequence of integers, is it the degree sequence of a graph? Clearly, if the sum of the sequence is odd, the answer is no. If the sum is even, it is not too hard to see that the answer is yes, provided we allow loops and multiple edges. The sequence need not be the degree sequence of a simple graph; for example, it is not hard to see that no simple graph has degree sequence $0,1,2,3,4$. A sequence that is the degree sequence of a simple graph is said to be graphical. Graphical sequences have been characterized; the most well known characterization is given by this result:
Theorem 5.1.3 A sequence $d_1\ge d_2\ge \ldots\ge d_n$ is graphical if and only if $\sum_{i=1}^n d_i$ is even and for all $k\in \{1,2,\ldots,n\}$, $$\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n \min(d_i,k).$$ $\qed$
It is not hard to see that if a sequence is graphical it has the property in the theorem; it is rather more difficult to see that any sequence with the property is graphical.
What does it mean for two graphs to be the same? Consider these three graphs: $$\eqalign{ G_1&=(\{v_1,v_2,v_3,v_4\},\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_2,v_4\}\})\cr G_2&=(\{v_1,v_2,v_3,v_4\},\{\{v_1,v_2\},\{v_1,v_4\},\{v_3,v_4\},\{v_2,v_4\}\})\cr G_3&=(\{w_1,w_2,w_3,w_4\},\{\{w_1,w_2\},\{w_1,w_4\},\{w_3,w_4\},\{w_2,w_4\}\})\cr }$$ These are pictured in figure 5.1.4. Simply looking at the lists of vertices and edges, they don't appear to be the same. Looking more closely, $G_2$ and $G_3$ are the same except for the names used for the vertices: $v_i$ in one case, $w_i$ in the other. Looking at the pictures, there is an obvious sense in which all three are the same: each is a triangle with an edge (and vertex) dangling from one of the three vertices. Although $G_1$ and $G_2$ use the same names for the vertices, they apply to different vertices in the graph: in $G_1$ the "dangling'' vertex (officially called a pendant vertex) is called $v_1$, while in $G_2$ it is called $v_3$. Finally, note that in the figure, $G_2$ and $G_3$ look different, even though they are clearly the same based on the vertex and edge lists.
So how should we define "sameness'' for graphs? We use a familiar term and definition: isomorphism.
Definition 5.1.4 Suppose $G_1=(V,E)$ and $G_2=(W,F)$. $G_1$ and $G_2$ are isomorphic if there is a bijection $f\colon V\to W$ such that $\{v_1,v_2\}\in E$ if and only if $\{f(v_1),f(v_2)\}\in F$. In addition, the repetition numbers of $\{v_1,v_2\}$ and $\{f(v_1),f(v_2)\}$ are the same if multiple edges or loops are allowed. This bijection $f$ is called an isomorphism. When $G_1$ and $G_2$ are isomorphic, we write $G_1\cong G_2$. $\square$
Each pair of graphs in figure 5.1.4 are isomorphic. For example, to show explicitly that $G_1\cong G_3$, an isomorphism is $$\eqalign{ f(v_1)&=w_3\cr f(v_2)&=w_4\cr f(v_3)&=w_2\cr f(v_4)&=w_1.\cr }$$
Clearly, if two graphs are isomorphic, their degree sequences are the same. The converse is not true; the graphs in figure 5.1.5 both have degree sequence $1,1,1,2,2,3$, but in one the degree-2 vertices are adjacent to each other, while in the other they are not. In general, if two graphs are isomorphic, they share all "graph theoretic'' properties, that is, properties that depend only on the graph. As an example of a non-graph theoretic property, consider "the number of times edges cross when the graph is drawn in the plane.''
In a more or less obvious way, some graphs are contained in others.
Definition 5.1.5 Graph $H=(W,F)$ is a subgraph of graph $G=(V,E)$ if $W\subseteq V$ and $F\subseteq E$. (Since $H$ is a graph, the edges in $F$ have their endpoints in $W$.) $H$ is an induced subgraph if $F$ consists of all edges in $E$ with endpoints in $W$. See figure 5.1.6. Whenever $U\subseteq V$ we denote the induced subgraph of $G$ on vertices $U$ as $G[U]$. $\square$
A path in a graph is a subgraph that is a path; if the endpoints of the path are $v$ and $w$ we say it is a path from $v$ to $w$. A cycle in a graph is a subgraph that is a cycle. A clique in a graph is a subgraph that is a complete graph.
If a graph $G$ is not connected, define $v\sim w$ if and only if there is a path connecting $v$ and $w$. It is not hard to see that this is an equivalence relation. Each equivalence class corresponds to an induced subgraph $G$; these subgraphs are called the connected components of the graph.
Exercises 5.1
Ex 5.1.1 The complement $\overline G$ of the simple graph $G$ is a simple graph with the same vertices as $G$, and $\{v,w\}$ is an edge of $\overline G$ if and only if it is not an edge of $G$. A graph $G$ is self-complementary if $G\cong \overline G$. Show that if $G$ is self-complementary then it has $4k$ or $4k+1$ vertices for some $k$. Find self-complementary graphs on 4 and 5 vertices.
Ex 5.1.2 Prove that if $\sum_{i=1}^n d_i$ is even, there is a graph (not necessarily simple) with degree sequence $d_1,d_2,\ldots,d_n$.
Ex 5.1.3 Suppose $d_1\ge d_2\ge\cdots\ge d_n$ and $\sum_{i=1}^n d_i$ is even. Prove that there is a multigraph (no loops) with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $d_1\le \sum_{i=2}^n d_i$.
Ex 5.1.4 Prove that $0,1,2,3,4$ is not graphical.
Ex 5.1.5 Is $4,4,3,2,2,1,1$ graphical? If not, explain why; if so, find a simple graph with this degree sequence.
Ex 5.1.6 Is $4,4,4,2,2$ graphical? If not, explain why, and find a multigraph (no loops) with this degree sequence; if so, find a simple graph with this degree sequence.
Ex 5.1.7 Prove that a simple graph with $n\ge 2$ vertices has two vertices of the same degree.
Ex 5.1.8 Prove the "only if'' part of theorem 5.1.3.
Ex 5.1.9 Show that the condition on the degrees in theorem 5.1.3 is equivalent to this condition: $\sum_{i=1}^n d_i$ is even and for all $k\in \{1,2,\ldots,n\}$, and all $\{i_1,i_2,\ldots, i_k\}\subseteq [n]$, $$\sum_{j=1}^k d_{i_j}\le k(k-1)+ \sum_{i\notin \{i_1,i_2,\ldots, i_k\}} \min(d_i,k).$$ Do not use theorem 5.1.3.
Ex 5.1.10 Draw the 11 non-isomorphic graphs with four vertices.
Ex 5.1.11 Suppose $G_1\cong G_2$. Show that if $G_1$ contains a cycle of length $k$ so does $G_2$.
Ex 5.1.12 Define $v\sim w$ if and only if there is a path connecting vertices $v$ and $w$. Prove that $\sim$ is an equivalence relation.
Ex 5.1.13 Prove the "if'' part of theorem 5.1.3, as follows:
The proof is by induction on $s=\sum_{i=1}^n d_i$. This is easy to see if $s=2$, so suppose $s>2$. Without loss of generality we may suppose that $d_n>0$. Let $t$ be the least integer such that $d_t>d_{t+1}$, or $t=n-1$ if there is no such integer. Let $d_t'=d_t-1$, $d_n'=d_n-1$, and $d_i'=d_i$ for all other $i$. Note that $d_1'\ge d_2'\ge\cdots d_n'$. We want to show that the sequence $\{d_i'\}$ satisfies the condition of the theorem, that is, that for all $k\in \{1,2,\ldots,n\}$, $$\sum_{i=1}^k d_i'\le k(k-1)+\sum_{i=k+1}^n \min(d_i',k).$$ There are five cases:
1. $k\ge t$
2. $k< t$, $d_k< k$
3. $k< t$, $d_k=k$
4. $k< t$, $d_n>k$
5. $k< t$, $d_k > k$, $d_n\le k$
By the induction hypothesis, there is a simple graph with degree sequence $\{d_i'\}$. Finally, show that there is a graph with degree sequence $\{d_i\}$.
This proof is due to S. A. Choudum, A Simple Proof of the Erdős-Gallai Theorem on Graph Sequences, Bulletin of the Australian Mathematics Society, vol. 33, 1986, pp. 67-70. The proof by Paul Erdős and Tibor Gallai was long; Berge provided a shorter proof that used results in the theory of network flows. Choudum's proof is both short and elementary.