
# 4.4: Introduction to Graph Theory

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

We can interpret the sdr problem as a problem about graphs. Given sets $$A_1,A_2,\ldots,A_n$$, with $$\bigcup_{i=1}^n A_i=\{x_1,x_2,\ldots,x_m\}$$, we define a graph with $$n+m$$ vertices as follows: The vertices are labeled $$\{A_1,A_2,\ldots,A_n,x_1,x_2,\ldots x_m\}$$, and the edges are $$\{\{A_i,x_j\}\mid x_j\in A_i\}$$.

Example 4.4.1 Let $$A_1=\{a,b,c,d\}$$, $$A_2=\{a,c,e,g\}$$, $$A_3=\{b,d\}$$, and $$A_4=\{a,f,g\}$$. The corresponding graph is shown in figure 4.4.1.

Figure 4.4.1. A set system depicted as a bipartite graph.

Before exploring this idea, we introduce a few basic concepts about graphs. If two vertices in a graph are connected by an edge, we say the vertices are adjacent. If a vertex $$v$$ is an endpoint of edge $$e$$, we say they are incident. The set of vertices adjacent to $$v$$ is called the neighborhood of $$v$$, denoted $$N(v)$$. This is sometimes called the open neighborhood of $$v$$ to distinguish it from the closed neighborhood of $$v$$, $$N[v]=N(v)\cup\{v\}$$. The degree of a vertex $$v$$ is the number of edges incident with $$v$$; it is denoted $$\d(v)$$.

Some simple types of graph come up often: A path is a graph $$P_n$$ on vertices $$v_1,v_2,\ldots,v_n$$, with edges $$\{v_i,v_{i+1}\}$$ for $$1\le i\le n-1$$, and no other edges. A cycle is a graph $$C_n$$ on vertices $$v_1,v_2,\ldots,v_n$$ with edges $$\{v_i,v_{1+(i\bmod n)}\}$$ for $$1\le i\le n$$, and no other edges; this is a path in which the first and last vertices have been joined by an edge. (Generally, we require that a cycle have at least three vertices. If it has two, then the two are joined by two distinct edges; when a graph has more than one edge with the same endpoints it is called a multigraph. If a cycle has one vertex, there is an edge, called a loop, in which a single vertex serves as both endpoints.) The length of a path or cycle is the number of edges in the graph. For example, $$P_1$$ has length 0, $$C_1$$ has length 1. A complete graph $$K_n$$ is a graph on $$v_1,v_2,\ldots,v_n$$ in which every two distinct vertices are joined by an edge. See figure 4.4.2 for examples.

Figure 4.4.2. Graphs $$P_5$$, $$C_6$$, $$K_5$$.

The graph in figure 4.4.1 is a bipartite graph.

Definition 4.4.2 A graph $$G$$ is bipartite if its vertices can be partitioned into two parts, say $$\{v_1,v_2,\ldots,v_n\}$$ and $$\{w_1,w_2,\ldots,w_m\}$$ so that all edges join some $$v_i$$ to some $$w_j$$; no two vertices $$v_i$$ and $$v_j$$ are adjacent, nor are any vertices $$w_i$$ and $$w_j$$.

The graph in figure 4.4.1 is bipartite, as are the first two graphs in figure 4.4.2.