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.

An easy consequence of this theorem:

Corollary 5.1.2 The number of odd numbers in a degree sequence is even.

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 be 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).$$

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$.

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]$.

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.