\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section3.4Subgraphs and Isomorphic Graphs
There are many different ways to draw a graph. Suppose that you and I each draw a graph and our graph drawings look different. How do we know if our graphs are actually the same graph (isomorphic)? For example, are any of the graphs \(G_1\text{,}\)\(G_2\text{,}\) and \(G_3\) drawn in Figure 3.4.1 the same (isomorphic)?
Recognizing when two apparently different objects are, for all mathematical purposes, the same or different is a powerful skill. For example, suppose that we are modeling a problem and encounter a new graph \(G\text{,}\) a graph that we know nothing about. But then we realize that \(G\) is isomorphic to a graph \(H\) that we know well. Then everything that is true about the known graph \(H\) is automatically true for the new graph \(G\) as well. The concept of isomorphic occurs throughout mathematics.
There is no known efficient algorithm for determining if two graphs are isomorphic. We begin this section with a visualization tool that can help and close this section by introducing vocabulary about graphs that live within other graphs (subgraphs), which can also offer clues about whether two graphs are isomorphic.
When we draw a graph, it is acceptable to have edges that cross each other. Any point of intersection of those edges in the drawing is not a vertex. For example, the complete graph \(K_5\) is typically drawn with many edges crossing, as in Figure 3.4.2.
In some situations, we might prefer to draw a graph without edges crossing. For example, if the graph were modeling a physical system, such as train tracks or electrical wires, we might want to avoid edge crossings, or at least find a drawing with as few edge crossings as possible. It is reasonable to ask whether a graph can be drawn without crossings. For example, can you find a way to draw \(K_5\) without any edge crossings?
A graph is planar if it can be drawn in the plane without any edge crossings. For example, consider the graph \(G\) drawn in Figure 3.1.4. In the fourth drawing of \(G\text{,}\) the edges \(\{3,4\}\) and \(\{1,2\}\) cross, but no edges cross in the first three drawings of \(G\text{.}\) Thus, \(G\) is planar.
A graph is nonplanar if it cannot be drawn in the plane without any edge crossings. For example, it turns out that the complete graph \(K_5\) is nonplanar.
Planarity game by Jason Davies lets you try your hand at moving planar graphs around until they appear without edge crossings. Play the game at level five and then at level eight.
Redraw the Harary graph \(H_{4,6}\) without edge crossings, using the vertex labels from Figure 3.4.7. Note: It is possible to draw \(H_{4,6}\) without edge crossings using only straight lines for edges, but you are welcome to use curves to represent edges instead.
Figure3.4.7.The Harary graph \(H_{4,6}\) drawn with multiple edge crossings.
The three graphs in Figure 3.4.1 have many common properties. For example, each graph has six vertices, five edges, and degree sequence 3, 2, 2, 1, 1, 1. They also all have chromatic number two. But they are not all isomorphic.
Two graphs \(G\) and \(H\) are isomorphic, denoted \(G \cong H\text{,}\) if it is possible to label the vertices of \(G\) and the vertices of \(H\) in such a way that \(G\) and \(H\) have the same set of vertices and the same set of edges. For example, the graphs \(G_1\) and \(G_2\) in Figure 3.4.1 are isomorphic. We show a common vertex labeling in Figure 3.4.9. You can check that each graph has the vertex set
\begin{equation*}
\{a, b, c, d, e, x\}
\end{equation*}
A planarity-style move on a graph drawing consists of moving one vertex \(v\) to a different location and redrawing the edges from \(v\) in its new location to each of \(v\)’s neighbors. 1
These moves are named for the game “Planarity” from Activity 3.4.A.
Graphs \(G\) and \(H\) are isomorphic exactly when we can transform a graph drawing of \(G\) into a graph drawing of \(H\) using a sequence of planarity-style moves. While visualizing such a transformation is a useful way to decide if two graphs are isomorphic, to prove that two graphs are isomorphic, you need to label the vertices according to the definition. If you can see the transformation, just follow the vertices to see what the labels should be. For example, we can think of transforming the graph \(G_1\) into the graph \(G_2\) from Definition 3.4.8 by shifting the vertex \(x\) up and to the right and the vertices \(d\) and \(e\) down and to the left.
When two graphs are complicated, it can be useful to compare their complements instead. Note that if \(G\) and \(H\) are isomorphic and labeled with the same vertices and edges, then that labeling shows that \(\overline{G}\) and \(\overline{H}\) have the same vertices and edges and so \(\overline{G}\) and \(\overline{G}\) are also isomorphic. We have the following result.
Label the vertices of the complements to show \(\overline{G} \cong \overline{H}\text{.}\)Solution.
We label the isolated vertex \(z\text{,}\) the degree 3 vertex \(a\text{,}\) and the degree 2 vertex \(b\text{.}\) There is one leaf adjacent to \(b\) which we label \(c\text{.}\) Last, we label the other two leaves \(u\) and \(v\) (in either order). Figure 3.4.15 shows these complements labeled as well as a simplified graph drawing of the complement.
Show that the graphs drawn in Figure 3.4.20 are isomorphic by labeling the vertices so they have the same edges. Hint: start with a 6-cycle in the graph on the left.
Figure3.4.20.Two drawings of the Petersen graph for Activity 3.4.B(d) and Exercise 8.
A common type of graph used to store information in a computer is a tree. We saw examples of possibility trees in Section 2.1. Trees are defined using the concepts of subgraph and connectivity, so we start there.
The graph \(H\) is a subgraph of the graph \(G\) if each vertex of \(H\) is a vertex of \(G\) and each edge of \(H\) is an edge of \(G\text{.}\) Note that since \(H\) is a graph, each edge of \(H\) necessarily contains two vertices of \(H\text{.}\) For example, in Figure 3.4.22, the graph on the left is a subgraph of the graph on the right.
The cycle \(C\) is a subgraph of \(G\) because each of \(C\)’s vertices (\(b\text{,}\)\(c\text{,}\)\(d\text{,}\) and \(e\)) and each of \(C\)’s edges (\(\{b,c\}\text{,}\)\(\{c,d\}\text{,}\)\(\{d,e\}\text{,}\) and \(\{e,b\}\)) are in \(G\text{.}\) Note that \(C\) is the cycle \(C_4\text{,}\) so we say \(C_4\) is a subgraph of \(G\text{.}\)
The path \(P\) is a subgraph of \(F\) because each of \(P\)’s vertices (\(a\text{,}\)\(c\text{,}\)\(d\text{,}\)\(e\text{,}\) and \(f\)) and each of \(P\)’s edges (\{f,c\}, \{c,b\}, \{b,e\}, and \{e,a\}) are in \(F\text{.}\) Note that \(P\) is the path \(P_5\text{,}\) so we say \(P_5\) is a subgraph of \(G\text{.}\)
A cyclic subgraph of a graph is a subgraph that is a copy of \(C_s\) for some integer \(s \ge 3\text{.}\) For example, the graph \(C\) from Example 3.4.23 was a cyclic subgraph of the graph \(G\text{.}\)
A graph \(G\) contains an \(s\) cycle if \(C_s\) is a subgraph for some \(s \ge 3\text{.}\) For example, the graph \(G\) in Figure 3.4.22 contains several 3-cycles, a couple of 4-cycles, and 5-cycle.
First, there are three 3-cycles: one with vertices \(a\text{,}\)\(b\text{,}\) and \(e\text{;}\) a second with vertices \(b\text{,}\)\(d\text{,}\) and \(e\text{;}\) and a third with vertices \(b\text{,}\)\(c\text{,}\) and \(d\text{.}\)
Next, there are two 4-cycles: one with vertices \(a\text{,}\)\(b\text{,}\)\(d\text{,}\) and \(e\) and the other with vertices \(b\text{,}\)\(c\text{,}\)\(d\text{,}\) and \(e\text{.}\)
In most networks, we want to maintain connectivity. Casually speaking, a graph is connected if there are no separate pieces, which is difficult to define directly. We give a formal definition of connected here.
A path in a graph is a subgraph that is a copy of \(P_s\) for some integer \(s \ge 1\text{.}\) For example, the graph \(P\) from Example 3.4.23 was a path in the graph \(G\text{.}\)
A \(uv\)-path is a path with endpoints \(u\) and \(v\text{.}\) For example, the graph \(P\) from Example 3.4.23 is a \(fa\)-path (or an \(af\)-path) in the graph \(G\text{.}\) A single vertex \(u\) is considered a \(uu\)-path.
A graph \(G\) is connected if for all vertices \(u\text{,}\)\(v\) there exists a \(uv\)-path in \(G\text{.}\) For example, the graph \(G\) in Figure 3.4.22 is connected, as are its subgraphs \(C\) and \(P\) from Example 3.4.23.
A graph \(G\) that is not connected is disconnected. For example, the subgraph \(D\) in Example 3.4.23 was disconnected because, for example, there does not exist a \(cd\)-path in \(D\text{.}\)
A tree is an connected acyclic graph. For example, the path graphs \(P_s\) are trees for \(s \ge 1\text{.}\) The graph \(T\) drawn in Figure 3.4.34 is also a tree.
The graph \(G\) is connected, but it is not a tree because it is not acyclic. For example, \(G\) contains a 3-cycle with vertices \(i\text{,}\)\(j\text{,}\) and \(h\text{.}\) By the way, \(G\) also contains a 4-cycle with vertices \(b\text{,}\)\(c\text{,}\)\(h\text{,}\) and \(i\) and a 5-cycle with vertices \(b\text{,}\)\(c\text{,}\)\(h\text{,}\)\(i\text{,}\) and \(j\text{.}\)
Hint: There is one vertex of degree four, so label that vertices \(x\) in each graph. The other four vertices \(a\text{,}\)\(b\text{,}\)\(c\text{,}\) and \(d\) form a 4-cycle in each graph.
Show that the graphs drawn in Figure 3.4.20 are isomorphic by labeling the vertices so that they have the same edges. Hint: Start with a 6-cycle in the graph on the left. Yes, this exercise repeats Activity 3.4.B(d).
Hint: The path \(P_4\) is the graph \(G\) shown in Figure 3.1.31. Its complement is shown in Figure 3.1.32, but you will need to re-label it to match \(P_4\text{.}\)
Hint: The cycle \(C_5\) is the graph \(H\) shown in Figure 3.1.31. Its complement is shown in Figure 3.1.32, but you will need to re-label it to match \(C_5\text{.}\)
If \(G\) is a self-complementary graph with four vertices, how many edges must it have? Explain. Hint: How many edges does the complete graph \(K_4\) have?
If \(G\) is a self-complementary graph with five vertices, how many edges must it have? Explain. Hint: How many edges does the complete graph \(K_5\) have?
Again, consider the graphs \(A\text{,}\)\(B\text{,}\) and \(C\) drawn in Figure 3.4.55. List seven different \(bh\)-paths in \(A\text{.}\) Hint: Some begin \(ba\ldots\) and some begin \(bc\ldots\text{.}\) Note: There are more than seven — can you find them all?
A caterpillar is a tree such that if we remove each leaf and its corresponding edge, then we get a path. For example, the graph drawn on the far right in Figure 3.4.37 is a caterpillar because when we remove the leaves (\(z\text{,}\)\(a\text{,}\) and \(c\)) and their corresponding edges, we get the path \(by\text{.}\)
Is the graph \(T\) drawn in Figure 3.4.34 a caterpillar? Justify your answer.
Hint: The leaves are \(n\text{,}\)\(p\text{,}\)\(q\text{,}\)\(r\text{,}\)\(t\text{,}\)\(v\text{,}\) and \(z\text{.}\) Decide if what remains when they are removed is a path. If so, then the tree is a caterpillar.
In a connected graph \(G\text{,}\) the distance between vertices \(v\) and \(w\), denoted \(\fn{d}(v,w)\text{,}\) is the number of edges of the shortest \(vw\)-path in \(G\text{.}\)
Find each distance in the graph \(G\) drawn in Figure 3.3.36 (in Exercise 13 of Section 3.2): \(\fn{d}(v_1,v_8)\text{,}\)\(\fn{d}(v_1,v_5)\text{,}\)\(\fn{d}(v_4,v_6)\text{,}\)\(\fn{d}(v_3,v_3)\text{.}\)
