Worksheet 4.4.1 Worksheet
Guiding Questions.
In this section, we’ll seek to answer the questions:
In
Section 2.1, we began exploring the idea of a graph. Giving a precise definition of a graph requires the use of sets, which we explore below. This more precise approach affords us several advantages, including providing a language for defining certain families of graphs, as well as suggesting intuitive meanings for important ideas like equality.
Definition 4.4.1.
A (finite simple) graph is an ordered pair \(G = (V,E)\text{,}\) where \(V\text{,}\) called the vertex set, is a finite set whose elements are called vertices, and \(E\text{,}\) called the edge set, consists of two-element subsets of \(V\text{.}\)
Activity 4.4.2.
Activity 4.4.3.
A few observations are in order.
Note that
Definition 4.4.1 defines a graph as an ordered pair of sets. The vertex set comes first, then the edge set.
Neither the set of vertices nor the set of edges is assumed to be nonempty. What does it mean for \(V = \emptyset\text{?}\) What if \(E = \emptyset\text{?}\)
However, if \(E\) is nonempty, we must have \(|V| \ge 2\) (why?).
The language of set theory enables us to precisely and economically define important graph-theoretic concepts. For instance: what does it mean for two graphs to be equal?
Definition 4.4.4.
Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) be graphs. We say \(G_1\) and \(G_2\) are equal, written \(G_1 = G_2\text{,}\) if \(V_1 = V_2\) and \(E_1 = E_2\) (as sets).
Thus, two graphs that look “the same” but have differently-named vertices are not equal; we will more precisely describe their “sameness” in
Chapter 5.
Definition 4.4.5.
Let \(G = (V,E)\) be a graph. The complement of \(G\), denoted \(G^c\text{,}\) is the graph with vertex set \(V\) and edge set
\begin{equation*}
E(G^c) := \setof{\set{x,y}}{x,y\in V, x\ne y, \set{x,y}\notin E}.
\end{equation*}
In some sense, then, given a graph \(G\text{,}\) the \(E(G^c) = E(G)^c\) assuming the universe in which the complement is being calculated is the collection of all 2-element subsets of \(V\text{.}\)
Problem 4.4.6.
Calculate the complements of each of the first five graphs in
Problem 2.1.1. What information would you need in order to calculate the complement of the last one?
Theorem 4.4.7.
Let \(G = (V,E)\) be a graph. Then \((G^c)^c = G\text{.}\)
Theorem 4.4.8.
Let \(G = (V,E_1)\) and \(H = (V,E_2)\) be graphs on the same vertex set \(V\text{.}\) Then \(G = H\) if and only if \(G^c = H^c\text{.}\)
Before introducing an important class of graphs we make one more set-theoretic definition (which will also be useful in
Chapter 5).
Definition 4.4.9.
Let \(X\) be a nonempty set. We say that a family of nonempty subsets \(\set{A_\alpha}_{\alpha\in\Lambda}\) of \(X\) is a partition of \(X\) provided:
\(\bigcup\limits_{\alpha\in\Lambda} A_\alpha = X\text{,}\) and
given \(\alpha,\beta\in\Lambda\) with \(\alpha\ne \beta\text{,}\) \(A_\alpha \cap A_\beta = \emptyset\text{.}\)
The sets \(A_\alpha\) are sometimes called the parts of the partition.
That is, the partition “splits” \(X\) into a family of disjoint subsets. We are often interested in partitions into finitely many subsets.
Definition 4.4.10.
Let \(G = (V,E)\) be a nonempty graph.
We say that \(G\) is bipartite if there is a partition \(V = X_1 \cup X_2\) of \(V\) such that if \(e \in E\) we have \(e\cap X_1 \ne \emptyset\) and \(e\cap X_2 \ne \emptyset\text{.}\)
We further say that \(G\) is a complete bipartite graph if there is a partition \(V = X_1\cup X_2\) of \(V\) such that for all two-element subsets \(e\subseteq V\) we have \(e\in E\) if and only if \(e\cap X_1 \ne \emptyset\) and \(e\cap X_2 \ne \emptyset\text{.}\) If \(|X_1| = m\) and \(|X_2| = n\text{,}\) we denote \(G\) by \(K_{m,n}\text{.}\)
We say that \(G\) is \(k\)-partite if there is a partition \(V = X_1 \cup X_2 \cup \cdots \cup X_k\) of \(V\) such that if \(e\in E\) there exist \(i, j\in\N, 1\le i \lt j \le k\) with \(e\cap X_i \ne \emptyset\) and \(e\cap X_j\ne \emptyset\text{.}\)
Finally, we say that \(G\) is a complete \(k\)-partite graph if there is a partition \(V = X_1 \cup X_2 \cup \cdots \cup X_k\) of \(V\) such that for all two element subsets \(e\subseteq V\text{,}\) \(e\in E\) if and only if there exist \(i, j\in\N, 1\le i \lt j \le k\) with \(e\cap X_i \ne \emptyset\) and \(e\cap X_j\ne \emptyset\text{.}\)
Activity 4.4.11.
Draw an example of a bipartite graph and a (different) complete bipartite graph. Make sure you can explain why your examples meet the definitions.
Activity 4.4.12.
Draw an example of a \(k\)-partite graph (for some \(k\in \N, k\ge 3\)) and a (different) complete \(k\)-partite graph. Make sure you can explain why your examples meet the definitions.
As a preview of some of the questions we’ll hope to explore in
Chapter 6, we introduce a new graph-theoretic concept.
Definition 4.4.13.
Let \(G = (V,E)\) be a graph. We say a nonempty subset \(C\subseteq V\) is a clique (pronounced “kleek”) if for all \(x,y\in C\) with \(x\ne y\) we have \(\set{x,y}\in E\text{.}\) That is, every pair of distinct vertices in \(C\) are adjacent.
The
clique number of
\(G\text{,}\) denoted
\(\omega(G)\text{,}\) is the
cardinality of the largest clique in
\(G\text{.}\)
LaTeX Code 4.4.14.
To typeset \(\omega(G)\) in \(\LaTeX\text{,}\) use \omega(G) in math mode.
Activity 4.4.15.
Theorem 4.4.16.
Let \(G = (V,E)\) be a bipartite graph. Then \(\omega(G) \le 2\text{.}\)
Hint.
Problem 4.4.17.
In
Theorem 4.4.16, you showed that a bipartite graph cannot have a clique containing three vertices. Exhibit examples of bipartite graphs
\(G\) with
