# 4.5: Introduction to Graph Theory

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

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

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

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

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

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

$$\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 $$\PageIndex{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 $$\PageIndex{1}$$.

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 $$\text{d}(v)$$.

This page titled 4.5: Introduction to Graph Theory is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.