Section 1.2 Definitions
Activity 5.
For now, let's say that a graph is simply a collection of vertices, some of which are connected by an edge. Draw all graphs that have exactly five vertices and six edges. How many are there? How do you know?
Activity 6.
Which (if any) of the graphs below are the same?
The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same?
You might also think of a graph as a set of vertices and a set of edges, where each edge is a set of two vertices. Are the graphs below the same or different?
- Graph 1:
-
\(V = \{a, b, c, d, e\}\text{,}\)
\(E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{.}\)
- Graph 2:
-
\(V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}\)
\(E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}\)
Subsection 1.2.1 The Definition of a Graph
Before we start studying graphs, we need to agree upon what a graph is. While we almost always think of graphs as pictures (dots connected by lines) this is fairly ambiguous. Do the lines need to be straight? Does it matter how long the lines are or how large the dots are? Can there be two lines connecting the same pair of dots? Can one line connect three dots?
The way we avoid ambiguities in mathematics is to provide concrete and rigorous definitions. Crafting good definitions is not easy, but it is incredibly important. The definition is the agreed upon starting point from which all truths in mathematics proceed. Is there a graph with no edges? We have to look at the definition to see if this is possible.
We want our definition to be precise and unambiguous, but it also must agree with our intuition for the objects we are studying. It needs to be useful: we could define a graph to be a six legged mammal, but that would not let us solve any problems about bridges.
Activity 7.
Write a definition for a graph. Make sure that your definition can be helpful in making sense of Activity 6.
Writing definitions is hard. You should compare what you came up with to the following:
Definition 1.2.1.
A graph is an ordered pair \(G = (V, E)\text{,}\) where \(V = \{v_1, v_2, ...\}\) is a set of vertices and \(E \subseteq \{\{a,b\} \st a, b \in V; a \ne b\}\) is a set of edges whose endpoints are vertices in \(V\text{.}\)
Does this definition match up with our intuitive understanding of what a graph is? Let's consider a few examples of what count as a graph according to the definition.
Example 1.2.2.
From our definition, the following is a graph: \(G = \{a, b, c, d, \{ab, ad, bd, dc\}\}\) Where here we have four vertices labeled \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\) with four edges \(ab\text{,}\) \(ad\text{,}\) \(bd\text{,}\) and \(cd\text{.}\) This meets our definition of a graph, but it does not look like a collection of vertices and edges. Instead, lets look at a visual representation of this graph \(G\text{.}\)
Now, the following pictorial representation is not a graph according to our current definition because there is a loop off of vertex \(a\) and two vertices connected with two edges \(dc\) and \(cd\text{.}\)
Subsection 1.2.2 Equality and Isomorphism
Now that we have a definition of a graph, we can say what it means for two graph to be equal.
Definition 1.2.3.
We say that graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are equal provided they have the same set of vertices and the same set of edges; that is, \(V_1 = V_2\) and \(E_1 = E_2\text{.}\)
Example 1.2.4.
These two graphs are equal:
However, these three graphs are not equal, even though they look very similar:
The second pair of graphs above really should be “the same” but they are not equal, by our definition. What are we to make of this?
This phenomenon is not unique to graphs. In algebra, we might ask how many groups have order 4. We should answer two: \(\Z_4\) and \(\Z_2\times \Z_2\text{.}\) But what about \(U(8)\) (the set \(\{1,3,5,7\}\) under multiplication mod 8)? What about the Klein 4-group? What about the subgroup of \(S_6\) consisting of the elements \(\{(1), (12), (34), (56)\}\text{?}\) What about the group of complex number \(\{1, -1, i, -i\}\) under multiplication? Aren't there infinitely many different groups of order 4?
How many vector spaces have dimension 3? How many complete graphs have order 5? (The order of a graph is the number of vertices; a graph is complete provided \(E = \{\{a,b\} \st a, b \in V; a \ne b\}\)).
The point is that it is natural and common to group mathematical objects by what makes them the same, and to call two non-identical versions of an object isomorphic. How should we define “isomorphic” for graphs?
Definition 1.2.5.
\(\phi\) is an isomorphism if for \(\phi : V_1 \rightarrow V_2\) there exists a bijection such that \(\{a,b\}\in E_1\) iff \(\{\phi(a),\phi(b)\}\in E_2 \)
Example 1.2.6.
The graphs below are not equal, but isomorphic because we can create a bijection where \(\phi(a)=e, \phi (b)=f, \phi (c)=g,\) and \(\phi (d)=h\text{.}\)
Note, that as always, “is isomorphic to” is an equivalence relation. [What does this mean and why do we know it? What are the implications? In particular, what do equivalence classes of graphs look like?]
Since we often conflate a graph with its drawing, and sometimes when we draw a graph, we label it, but not always, we should make a distinction between a labeled graph and an unlabeled graph. What even is an unlabeled graph?
We often speak of the complete graph on 5 vertices, and call this \(K_5\) (or in general, call the complete graph on \(n\) vertices \(K_n\)). We might draw \(K_5\) as in Figure 1.2.7. Is this even a graph though? What are the sets \(V\) and \(E\text{?}\)
[How do we reconcile the above with what we have said about isomorphism? Does it make sense to say that two unlabeled graphs are isomorphic? What could that mean?]
Activity 8.
How many copies of \(P_3\) are there in the graph \(K_5\text{?}\) (The graph \(P_3\) is the path of 4 vertices and 3 edges.)
How many copies of \(C_4\) are there in the graph \(K_5\text{?}\) (The graph \(C_4\) is the 4-cycle; you would draw it as a square and even call it a square.)
There are \(60\) copies of \(P_3\) in the graph \(K_5\text{.}\) An intuitive argument can be presented to justify this. Each path must start from \(1\) of \(5\) vertices (i.e. \({5 \choose 1}\)). Afterwhich, there are only \(4\) remaining vertices (i.e. \({4 \choose 1}\)) to choose a connection to via edge. This pattern continues up to a path of length 3, resulting in \({5 \choose 1}{4 \choose 1}{3 \choose 1}{2 \choose 1}=120\) choices, but there is an issue. Each of the desired paths are being counted twice due to a path and the reverse path being equivalent. This means the number of \(P_3\)s in the graph \(K_5\) is \(120/2=60\text{.}\)
There are \(30\) copies of \(C_4\) in the graph \(K_5\text{.}\) A similar argument to the one above can be made regarding the choice of vertices. The only difference is with the choice of the last vertex. Based on the definition of a cycle, it is a path that starts and stops at the same vertex, meaning that instead of choosing between the final \(2\) vertices when completing a \(P_3\text{,}\) one instead connects back to the starting vertex. This results in \({5 \choose 1}{4 \choose 1}{3 \choose 1}{1 \choose 1}/2=30\text{.}\) Again, we divide by \(2\) to avoid double counting.
Subsection 1.2.3 Subgraphs
The previous activity suggests that we need to careful about what we mean by one graph being “inside” another.
Definition 1.2.8.
We say that a graph \(H\) is a subgraph of \(G\) (written \(H \subseteq G\)) provided \(H\) is a graph and \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\text{.}\)
Note that \(V(G)\) is the set of vertices of \(G\) and \(E(G)\) is the set of edges of \(G\text{.}\)
It is often useful to think of a subgraph as the result of removing parts of a graph. What should we be allowed to remove? From the definition above, ...
Example 1.2.9.
Here is the graph \(K_6 \text{.}\)
The following are all subgraphs of the above graph.
Sometimes we want to remove some vertices but keep all of the relational structure of those vertices that remain. Thinking of the friendship model of graphs, you might wish to restrict your attention just to the students in a single course, instead of all math majors, but still be interested in all those friendships among those students.
Definition 1.2.10.
A subgraph \(H\subseteq G\) is an induced subgraph provided \(H\) is a subgraph of \(G\) such that if \(u,v \in V(H)\) and \(\{u,v\} \in E(G)\) then \(\{u,v\} \in E(H)\text{.}\)
Example 1.2.11.
Supposing \(K_6\) is our graph again. The graph on the left is not an induced graph where the graph on the right is. Why?
Is there an equivalent concept of subgraph where we specify edges to keep, and are forced to keep the required vertices? What would this be called?
Another important type of subgraph is one in which all the vertices of the original graph are included. We say that a subgraph \(H \subseteq G\) is spanning if \(V(H) = V(H)\) (i.e., if they have the same set of vertices).
Example 1.2.12.
Below is a spanning graph of \(K_6\text{.}\)
