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.
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{.}\)
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{?}\)
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?
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.
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{.}\)
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?
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{.}\)
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.
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.
