Skip to main content
πŸ”—

Section 5.2 Basic Definitions

πŸ”—
Video: Graph Theory Definitions

πŸ”—
We now formally state the definition of a graph. Unless otherwise specified, the graphs you will encounter in this text are simple graphs.

πŸ”—
Definition 5.2.1. Graph.

A graph G is defined as a pair G=(V,E) where V is a finite set consisting of elements called vertices, and E is a collection of unordered pairs of elements in V called edges.

If e=(u,v) is an edge of the graph, then we say that the vertices u and v are the endpoints of the edge e. The vertices u and v are called adjacent vertices; the edge e is also said to be incident to the vertices u and v.

πŸ”—
Definition 5.2.2. Simple Graphs and Multigraphs.

A graph G=(V,E) is a simple graph if E has no repeated elements, i.e., between every pair of vertices there is at most one edge. A graph that is permitted to have multiple edges between a pair of vertices is called a multigraph.

πŸ”—
Visually, a graph can be drawn by using points to represent its vertices, and lines connecting pairs of vertices to represent the edges.

Define the graph \(G\) to have vertices

\begin{equation*} V = \{v_1,v_2,v_3,v_4,v_5\} \end{equation*}

and edges

\begin{equation*} E = \{(v_1,v_2),(v_1,v_3),(v_1,v_4),(v_2,v_5),(v_4,v_5)\}\text{.} \end{equation*}

We can represent this graph by labeling five nodes, and drawing each edge.

Draw each of the following graphs:

  1. \(G_1 = (V_1, E_1)\) where \(V_1 = \{p, q, r, s, t, u\}\) and \(E_1 = \{(p,q),(q,r),(q,s),(q,t),(q,u),(r,s),(r,t),(r,u),(s,u)\}\text{.}\)
  2. \(G_2 = (V_2, E_2)\) where \(V_2 = \{1,2,3,4\}\) and \(E_2\) contains all pairs of elements from \(V_2\text{.}\)

List all elements in the vertex and edge sets of each graph below.

πŸ”—
Definition 5.2.6. Degree of a vertex.

The degree d(v) of a vertex v is the number of edges incident to it.

The degree sequence of a graph is the nonincreasing sequence of numbers formed by the degrees of its vertices.

πŸ”—
The degree sequence of a graph is a well-defined object, since the nonincreasing condition gives a canonical ordering of the vertex degrees to form the sequence.

In the graph of Example 5.2.3, the degrees of each vertex are:

Vertex \(v_1\) \(v_2\) \(v_3\) \(v_4\) \(v_5\)
Degree 3 2 1 2 2

We write this as \(d(v_1) = 3\text{,}\) \(d(v_2) = 2\text{,}\) and so on. Hence the degree sequence of the graph is 3, 2, 2, 2, 1 (just rearrange the numbers in nonincreasing order).

Determine the degrees of each vertex of the graphs \(G_1\text{,}\) \(G_2\text{,}\) \(G_3\text{,}\) and \(G_4\) from Checkpoint 5.2.4 and Checkpoint 5.2.5, then write the degree sequence of each graph.

In a graph, what does it mean for a vertex \(v\)to have degree \(d(v) = 0\text{?}\) Can you draw a graph with degree sequence 0, 0, 0, 0, 0?

πŸ”—
While it is easy to write the degree sequence of a given graph, it is much harder to start with a nonincreasing sequence and determine whether or not it is possible to draw a graph with that particular sequence of vertex degrees.

πŸ”—
From the next result we can derive one simple way to tell if given sequence cannot be realized as a graph. This will be our first graph theory proof: that the sum of the degrees of all vertices must be equal to twice the number of edges in the graph.

πŸ”—
Video: Handshake Lemma

If \((u,v)\) is an edge of \(G\text{,}\) then it contributes 2 to the sum of all vertex degrees (one to the degrees of each of its endpoints: \(d(u)\) and \(d(v)\)). This is true for all edges of \(G\text{,}\) so twice the number of edges must be exactly the sum of all degrees.

πŸ”—
Remark 5.2.11.

In the above statement we used the notation V(G) to refer to the vertex set of G; we will also use the notation E(G) to refer to the collection of edges of G. This notation comes in handy if we are talking about the vertex or edge sets of different graphs.

Use Theorem 5.2.10 to prove that any graph must have an even number of vertices with odd degree.

Explain how Checkpoint 5.2.13 implies that in a party, the number of people who shook hands with an odd number of other people's hands must be even.

πŸ”—
Because of Checkpoint 5.2.14, the result of Checkpoint 5.2.13 is sometimes called the Handshake Lemma. This can be used to prove that certain sequences will never occur as the degree sequence of a graph.

Checkpoint 5.1.5 can be resolved by arguing that the coauthorship relations among the six mathematicians can be represented using a graph: by taking the six mathematicians as vertices and placing an edge between two mathematicians if they have coauthored a paper together.

The sequence 3, 2, 2, 2, 1, 1 cannot be the degree sequence of this graph, since there is an odd number of vertices of odd degree. (There are three: 3, 1, 1.) Therefore someone must have made a mistake counting.

πŸ”—
Try proving the following basic properties about degree sequences.

Can a graph on 4 vertices have degree sequence 3, 2, 1, 0?

Is it possible for the numbers \(0\) and \(n-1\) to both occur in the degree sequence of a graph with \(n\) vertices? Prove your answer.

Show that the sum of the degrees of a simple graph cannot add up to more than \(n(n-1)\text{.}\)