3.4.1: Exercises

Math 104 Green · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under not declared, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    Use the figure to answer the following exercises. A pair of graphs is given. Identify three differences between them that demonstrate the graphs are not isomorphic.

    Six graphs. Graph G has four vertices, a, b, c, and d. The edges connect c a, a b, and b d. Graph H has four vertices, e, f, g, and h. The curved edges connect e g, g h, h f, and f e. Graph I has four vertices, i, j, k, and m. The edges connect i j, j, m k, k i, and i m. Graph J has three vertices: o, n, and p. The edges connect o n, n p, and p o. Graph K has three vertices, q, r, and s. The curved edges connect q r and r s. Graph L has four vertices, t, u, v, and w. The edges connect u v, v t, and t u.

    Exercise \(\PageIndex{1}\)

    G and H

    Exercise \(\PageIndex{2}\)

    G and I

    Exercise \(\PageIndex{3}\)

    G and J

    Exercise \(\PageIndex{4}\)

    G and K

    Exercise \(\PageIndex{5}\)

    G and L

    Exercise \(\PageIndex{6}\)

    H and I

    Exercise \(\PageIndex{7}\)

    H and J

    Exercise \(\PageIndex{8}\)

    H and K

    Exercise \(\PageIndex{9}\)

    H and L

    Exercise \(\PageIndex{10}\)

    I and J

    Exercise \(\PageIndex{11}\)

    I and K

    Exercise \(\PageIndex{12}\)

    I and L

    Exercise \(\PageIndex{13}\)

    J and K

    Exercise \(\PageIndex{14}\)

    K and L

    Use the figure to answer the following exercises. In each exercise, a pair of graphs is given. Determine if one graph is a subgraph of the other graph, or the two graphs are isomorphic.

    Seven graphs. Graph P has three vertices, a, b and c. The curved edges connect a b, b c, and c a. Graph Q has four vertices, e, f, g, and h. The edges connect d f, f g, g e, e d, and f e. Graph R has three vertices, h, i, and j. The edges connect h i, i j, and i h. Graph S has four vertices, k, l, m, and n. The edges connect l m, m n, n k, k l, l n, and k m. Graph T has four vertices, o, p, q, and r. The edges connect p q, q r, r o, o p, and p r. Graph U has four vertices, s, t, u, and v. The edges connect s t, t u, u v, v s, and s u. Graph V has four vertices, w, x, y, and z. The curved edges connect w x, x y, y z, and z w. The straight edges connect w y and x z.

    Exercise \(\PageIndex{15}\)

    P and Q

    Exercise \(\PageIndex{16}\)

    P and R

    Exercise \(\PageIndex{17}\)

    P and U

    Exercise \(\PageIndex{18}\)

    Q and R

    Exercise \(\PageIndex{19}\)

    Q and S

    Exercise \(\PageIndex{20}\)

    Q and T

    Exercise \(\PageIndex{21}\)

    Q and V

    Exercise \(\PageIndex{22}\)

    S and V

    Exercise \(\PageIndex{23}\)

    T and U

    Exercise \(\PageIndex{24}\)

    U and V

    Use the figure to answer the following exercises. In each exercise, a pair of graphs is given. Either give a reason that the graphs are not isomorphic, or show how one of the graphs can be transformed to look like the other.

    Four graphs. Graph A has six vertices: r, s, t, u, v, and w. The edges connect r s, s t, t w, w v, v u, and r v. Graph B has six vertices: a, b, c, d, e, and f. The edges connect a b, c d, e f, a f, e b, and e c. Graph C has six vertices: g, h, m, n, p, and q. The edges connect q m, q n, m g, g h, g p, and p n. Graph D has six vertices: i, j, k, x, y, and z. The edges connect k z, z y, y x, x i, i j, and j y.

    Exercise \(\PageIndex{25}\)

    A and B

    Exercise \(\PageIndex{26}\)

    A and C

    Exercise \(\PageIndex{27}\)

    A and D

    Exercise \(\PageIndex{28}\)

    B and C

    Exercise \(\PageIndex{29}\)

    B and D

    Exercise \(\PageIndex{30}\)

    C and D

    Use the figure to answer the following exercises. Determine if one graph is a subgraph of the other graph, or the two graphs are isomorphic. If they are isomorphic, name an isomorphism. If one is a subgraph of the other, indicate a correspondence between the vertices that demonstrates the relationship.

    Four graphs. Graph W hs five vertices: a, b, c, d, and e. The edges connect a b, b c, c d, d e, e a, and e b. Graph X has five vertices: f, g, h, i, and j. The edges connect f g, g h, h i, i j, j f, j g, and i g. Graph Y has five vertices: k, m, n, o, and p. The edges connect k p, p o, o n, n m, m k, and k n. Graph Z has five vertices: q, r, s, u, and t. The edges connect u r, u s, s r, r q, q t, r t, and s t.

    Exercise \(\PageIndex{31}\)

    W and Z

    Exercise \(\PageIndex{32}\)

    X and Y

    Exercise \(\PageIndex{33}\)

    X and Z

    Use the figure to answer the following exercises.

    Four graphs. Graph W hs five vertices: a, b, c, d, and e. The edges connect a b, b c, c d, d e, e a, and e b. Graph X has five vertices: f, g, h, i, and j. The edges connect f g, g h, h i, i j, j f, j g, and i g. Graph Y has five vertices: k, m, n, o, and p. The edges connect k p, p o, o n, n m, m k, and k n. Graph Z has five vertices: q, r, s, u, and t. The edges connect u r, u s, s r, r q, q t, r t, and s t.

    Exercise \(\PageIndex{34}\)

    Find the complement of Graph W.

    Exercise \(\PageIndex{35}\)

    Find the complement of Graph Y.

    Exercise \(\PageIndex{36}\)

    Find the complement of Graph X.

    Exercise \(\PageIndex{37}\)

    Find an isomorphism between the complement of W and the complement of Y if one exists. If not, explain how you know.

    Exercise \(\PageIndex{38}\)

    Are W and Y isomorphic? Explain how you know.

    Exercise \(\PageIndex{39}\)

    Find an isomorphism between the complement of W and the Complement of X if one Exists. If not, explain how you know.

    Exercise \(\PageIndex{40}\)

    Are W and X isomorphic? Explain how you know.

    Exercise \(\PageIndex{41}\)

    Find the complement of the graph in the given figure representing direct flights between south Florida airports. Explain what the graph represents.

    A graph represents the direct flights between South Florida airports. The graph has five vertices. Edges from the vertex, Tampa T P A connect with Key West E Y W, Miami M I A, Fort Lauderdale F L L, and West Palm Beach P B I. An edge from Fort Lauderdale connects with Key West. An edge from Miami connects with Key West.

    3.4.1: Exercises is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.