Math 4120: Graph Theory and Combinatorics

Basic Definitions and Examples
Subgraphs, Isomorphism, and Connectivity

1. Basic Definitions

The Definition of a Graph

A graph $ G $ consists of a vertex set $ V(G) $, whose elements are called vertices and an edge set $ E(G) $, where elements in $ E(G) $ are unordered pairs of vertices. The elements of $E(G)$ are called edges.

Remarks: Recall that an unordered pair is just any two-element set $\{ u , v \}$, where $u\ne v.$ For brevity, we often write such an edge more simply as $ uv $. In various contexts, it is common to denote an edge by the ordered pair $ (u,v) $. This leads to an alternative definition of a graph, equivalent to ours, as a relation on the vertex set $V(G)$ that is both symmetric (meaning that $ (u,v) $ is an edge if and only if $ (v,u) $ is an edge) and irreflexive (meaning that $ (u,u) $ is never an edge.)

Example 1:

The picture shown above is a visual representation of a graph with the $6$ vertices and $8$ edges given below. $ V(G) = \{1, 2, 3, 4, 5, 6\} $
$ E(G) = \{12, 13, 23, 34, 36, 46, 45, 56\} $.

Neighborhood and Degree

For any edge $ uv \in E(G) $, the vertices $ u, v \in V(G) $ are said to be adjacent and/or neighbors in $ G $. The vertices $ u, v $ are called the ends of the edge $ uv $, and any edge is said to be incident at either of its ends.

For any vertex $ u \in V(G) $, we define its neighborhood as the set $$ \Gamma(u) = \{ v \in V(G) \mid uv \in E(G) \}. $$ The degree of $ u $ is the integer $ d(u) = \#\Gamma(u) $, which counts the number of $u$'s neighbors.

Our notation for neighborhood and degree suppress the dependence on the graph $G,$ which is usually clear from the context. In cases where we must consider multiple graphs, we may instead write $\Gamma_G$ and $d_G.$

Example 1 (cont.):

Let us determine the degrees of all vertices in our running example:

$ \Gamma(1)=\{2,3\} \quad \Rightarrow \quad d(1)=2 $
$ \Gamma(2)=\{1,3\} \quad \Rightarrow \quad d(2)=2 $
$ \Gamma(3)=\{1,2,4,6\} \quad \Rightarrow \quad d(3)=4 $
$ \Gamma(5)=\{4,6\} \quad \Rightarrow \quad d(5)=2 $
$ \Gamma(6)=\{3,4,5\} \quad \Rightarrow \quad d(6)=3 $

Notice what happens if we sum over all six vertices' degrees: $ 2+2+4+3+2+3 = 16 = 2 \cdot \#E(G) $. This reflects a general fact called the handshaking lemma, which we prove below.

Variations on the Definition of a Graph

Our definition of a graph given above can be qualified by describing it as a simple, undirected graph.

Directed Graph (Digraph): Edges are ordered pairs, often denoted $ \overrightarrow{uv} $ (an edge directed from $ u$ to $ v $. Digraphs allow the possibility of loops, which are edges of the form $ \overrightarrow{uu} $. A digraph with no loops is essentially a graph if it has the property that $ \overrightarrow{uv} $ is a directed edge if and only if $ \overrightarrow{vu} $ is.
Multigraph: The same edge can appear more than once. More formally, an undirected multigraph consists of a vertex set $ V(G) $, edge set $ E(G) $, and incidence function $ \psi $ that takes edges to unordered pairs of vertices: if ordered pairs are used, one obtains a directed multigraph. In addition to loops, in a multiraph it is possible to have parallel edges, meaning $ e, e' \in E(G) $ such that $ \psi (e) = \psi (e') = uv. $ A multigraph is simple if it has no loops or parallel edges.

In this course, "graph" always means a simple, undirected graph. When the need to consider digraphs or multigraphs arises, we will explicitly use these terms.

The Handshaking Lemma

Theorem: For any graph $ G $, $$ \sum_{v \in V(G)} d(v) = 2 \cdot \#E(G) $$

One consequence of this result is the saying that "at any party, an even number of hands are shaken."

Proof: Consider the set of ordered pairs $$ S = \{ (u,v) \in V(G) \times V(G) \mid uv \in E(G) \} $$ We will count the elements of $ S $ in two different ways.

First way: For any vertex $ v \in V(G) $, there are exactly $ d(v) $ pairs $ (u,v) \in S $. Thus, $ \#S = \sum_{v \in V(G)} d(v) $.
Second way: Any edge $ uv \in E(G) $ contributes exactly two elements to $ S $, namely $ (u,v) $ and $ (v,u) $. Thus, $ \#S = 2 \cdot \#E(G) $.

Combining these finishes the proof.

Exercise How does the handshaking lemma generalize to digraphs and/or multigraphs?

2. Subgraphs, Isomorphism and Connectivity

Two Notions of Subgraph

A graph $ G' $ is a subgraph of $ G $ if $ V(G') \subseteq V(G) $ and $ E(G') \subseteq E(G) $.

For any subset of vertices $ U \subseteq V(G) $, we may form the induced subgraph $ G[U] $ with vertex set $ U $ and edge set $ \{ uv \in E(G) \mid u,v \in U \} $.

Consider the graph below:

Two of its induced subgraphs are shown below.

The next graph is an example of a non-induced subgraph.

Complete Graphs and Isomorphism

We say a graph is complete if any two of its vertices are adjacent. Thus, the number of edges in a complete graph on $ n $ vertices is equal to the binomial coefficient $ \binom{n}{2} = \frac{n (n-1)}{2}. $ An $ n $-vertex complete graph is also called an $n $-clique. The images below show $ n $-cliques for $n \in \{ 1,2,3,4 \} $.

$K_1$

$K_2$

$K_3$

$K_4$

Here is another image of a $4$-clique:

$K_4$

Notice that both $ 4 $-cliques are labelled as $ K_4 $, despite two notable differences between the pictures: namely, (1) the two graphs have different vertex labels, and (2) one clique is drawn with edge crossings, and the other is not. Note, however, that we could also draw the first four-clique without any crossings. Indeed, if we simply relabel the vertices $5,6,7,8$, respectively, by $1,2,3,4$, we will get the same vertices and edges.

All cliques of a given size are exactly the same up to relabeling: this is formalized by the notion of graph isomorphism. Recall that a bijection between two sets is a function that is one-to-one and onto. Two graphs $ G, H $ are isomorphic if there exists a bijection of vertex sets $ \iota : V(G) \to V (H) $ that preserves adjacency: $$ uv \in E(G) \quad \Leftrightarrow \quad \iota (u) \iota (v) \in E(H).$$

It is not always obvious when two graphs are isomorphic: consider, for example, the two isomorphic graphs shown below, where we may construct the following isomorphism: $$\iota (1)= 8, \quad \iota (2) = 10, \quad \iota (3) = 9, \quad \iota (4) = 6, \quad \iota (5) = 7. $$

For the $ 5 $-clique shown below, it turns out we cannot draw all $ 10 $ edges in the plane without crossings. Graphs which can be drawn in this way are said to be planar. Planar graphs are characterized by a theorem of Kuratowski, which we will discuss later in the course.

$K_5$

Paths, Cycles, and Connectivity

A path is a graph $ P $ of the form $ V(P) = \{x_0, \dots, x_l\} $ and $ E(P) = \{x_0x_1, x_1x_2, \dots, x_{l-1}x_l\} $, where all vertices $ x_i $ must be distinct. The number of edges is its length $ l $. A path may also be denoted by $ x_0 \dots x_l $. The vertices $ x_0, x_l $ are the ends of the path $ P $, which is also said to be a $ x_0 x_l $-path, or a path from $ x_0 $ to $ x_l) $. The ends of a path are the two unique degree-1 vertices: any other vertices must have degree 2.

Similarly, a cycle of length $ l $ is a graph $ C $ of length $ l $ with vertex set $ V(C) = \{ x_1, \dots, x_l\} $ and edge set $ E(C) = \{ x_1x_2, \dots, x_{l-1}x_l, x_l x_1 \}. $ All vertices in a cycle must have degree 2.

When we refer to a "path" or a "cycle" in a graph, one should think of a subgraph isomorphic to the path and cycle graphs defined above. In an $ n $-vertex graph, a Hamiltonian path is any path of length $ n-1 $, and a Hamiltonian cycle is any cycle of length $ n $. Currently, there is no known algorithm for efficiently detecting Hamiltonian paths or cycles in a graph: this is related to the famous unsolved P vs NP problem.

A graph $ G $ is connected if it contains a $ uv $-path for any $ u, v \in V(G) $. A maximal connected subgraph is a called a connected component. In most circumstances, if we have a graph with multiple connected components, it is better to think of the connected components separately as connected graphs.

Math 4120: Graph Theory and Combinatorics

Table of Contents

1. Basic Definitions

The Definition of a Graph

Example 1:

Neighborhood and Degree

Example 1 (cont.):

Variations on the Definition of a Graph

The Handshaking Lemma

2. Subgraphs, Isomorphism and Connectivity

Two Notions of Subgraph

Complete Graphs and Isomorphism

\(K_1\)

\(K_2\)

\(K_3\)

\(K_4\)

\(K_4\)

\(K_5\)

Paths, Cycles, and Connectivity