5.1: Discovering Graphs

Definitions are typically constructed after we work with new objects. The definition is constructed to match the properties we have observed and need. In this section we will practice this by developing a definition for a type of object known as a graph.

Figure $\PageIndex{1}$: Each of these is a graph

Figure $\PageIndex{2}$: None of these is a graph

Checkpoint $\PageIndex{3}$

Based on the examples in Figure $\PageIndex{1}$ and Figure $\PageIndex{2}$ determine which of the following are graphs.

Example $\PageIndex{4}$: Each of these is a graph.

Each of these is a graph.

1. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_3\}\\ q_3 & = \{p_2,p_3\} \end{align*}$$
2. $$\begin{align*} P & =\{p_1,p_2,p_3,p_4\}\\ Q & =\emptyset \end{align*}$$
3. $$\begin{align*} P & =\{p_1,p_2,p_3,p_4\}\\ Q & =\{q_1,q_2\}\\ q_1 &= \{p_1,p_3\}\\ q_2 & = \{p_2,p_4\} \end{align*}$$
4. $$\begin{align*} P & =\{p_1,p_2,p_3,p_4,p_5\}\\ L & =\{\ell_1,\ell_2,\ell_3,\ell_4,\ell_5,\ell_6\}\\ \ell_1 & = \{p_2,p_3\}\\ \ell_2 & = \{p_1,p_4\}\\ \ell_3 & = \{p_4,p_5\}\\ \ell_4 & = \{p_1,p_5\}\\ \ell_5 & = \{p_2,p_4\}\\ \ell_6 & = \{p_2,p_5\} \end{align*}$$
5. $$\begin{align*} V & =\{c,d,e,f\}\\ E & =\{\{c,d\}, \{d,e\}, \{e,f\},\\ & \{c,f\}\} \end{align*}$$
6. $$\begin{align*} V & =\{v_1,v_2,v_3,v_4\}\\ E & =\{\{v_1,v_2\}, \{v_1,v_3\}, \\ & \{v_2,v_3\}, \{v_2,v_4\}\} \end{align*}$$
7. $$\begin{align*} P & =\{p\}\\ Q & =\emptyset \end{align*}$$
8. $$\begin{align*} P & =\{q,r,s,t\}\\ Q &=\{\{q,r\}, \{r,t\}, \{q,t\}, \{r,s\}\} \end{align*}$$

Example $\PageIndex{5}$

None of these is a graph.

1. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_3,p_4\} \end{align*}$$
2. $$\begin{align*} P & =\{p_1,p_2\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_2\} \end{align*}$$
3. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 \&= (p_1,p_2)\\ q_2 & = (p_1,p_3)\\ q_3 & = (p_2,p_3) \end{align*}$$
4. $$\begin{align*} V & =\{x,y,z\}\\ E & =\{f,g,h\}\\ f & = (x,y)\\ g & = (y,x)\\ h & = (y,z) \end{align*}$$
5. $$\begin{align*} P & =\emptyset\\ Q & =\emptyset \end{align*}$$
6. $$\begin{align*} P \& =\{q,r,s,t\}\\ Q & =\{\{q,r\}, \{r,t\}, \{s\} \} \end{align*}$$
7. $$\begin{align*} V & =\{p_1,p_2,\ldots,p_n,\ldots\}\\ E & =\{\{p_1,p_2\}, \{p_2,p_4\}, \{p_1,p_3\}, \{p_4,p_6\}\} \end{align*}$$
8. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_3\} \end{align*}$$

Checkpoint $\PageIndex{6}$

Based on the examples in Example 5.1.4 and Example 5.1.5 determine which of the following are graphs.

1. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1\}\\ q_1 & = \{p_1,p_3\} \end{align*}$$
2. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\} \end{align*}$$
3. $$\begin{align*} V & =\{v_1,v_2,\ldots,v_n,\ldots\}\\ E & =\{e_1,e_2,\ldots,e_n,\ldots\}\\ e_1 & = (v_1,v_2)\\ \vdots\\ e_n & = (v_n,v_{n+1})\\ \vdots \end{align*}$$
4. $$\begin{align*} P & =\{p,q,r\}\\ Q & =\{t,u,v\}\\ t & = \{p,q\}\\ u & = \{p,r\}\\ v & = \{q,r\} \end{align*}$$
5. $$\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\emptyset \end{align*}$$
6. $$\begin{align*} V & =\{u_1,u_2,u_3,u_4\}\\ E & =\{(u_1,u_2), (u_2,u_1),\\ & (u_3,u_4)\} \end{align*}$$
7. $$\begin{align*} V & =\{v_1,v_2,v_3\}\\ E & =\{\{v_1,v_2\}, \{v_1,v_3\}, \{v_3\}\} \end{align*}$$
8. $$\begin{align*} P & =\{p,q,r,s\}\\ Q & =\{\{p,q\}, \{p,r\}, \{p,s\},\\ & \{q,r\}, \{q,s\}, \{r,s\}\} \end{align*}$$

Checkpoint $\PageIndex{7}$

In terms of the diagrams in Figure 5.1.1 list properties required and properties not allowed in graphs.

Checkpoint $\PageIndex{8}$

In terms of the sets in Example 5.1.4 list properties required and properties not allowed in graphs.

Checkpoint $\PageIndex{9}$

Draw the diagram form of the first graph in Example 5.1.4.

Checkpoint $\PageIndex{10}$

Write the set form of the fourth graph (bottom left) in Figure 5.1.1.