14.5: Activities

Elementary Foundations: An Introduction to Topics in Discrete Mathematics · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

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

    Activity \(\PageIndex{1}\)

    Draw all possible simple graphs with \(4\) vertices.

    Hint.

    See Statement 4 of Proposition 14.2.1.

    Activity \(\PageIndex{2}\)

    Suppose \(G = (V,E)\) is a graph. Decide the truth of the following statement.

    Every pair of a subset \(V' \subseteq V\) and a subcollection \(E' \subseteq E\) defines a subgraph \(G' = (V',E')\) of \(G\text{.}\)

    Activity \(\PageIndex{3}\)

    Draw a graph where the nodes are students present in today's class. Draw edges between pairs of students that are in the same group today. Additionally, draw an edge between a member of your group and another student if that pair was in a group together last class.

    Activity \(\PageIndex{4}\)

    For each of the following graphs, write out its formal definition as either a (regular) graph, a weigthed graph, or a directed graph, as appropriate.

    1. clipboard_e6a611eefb51ea6a8a0a882b5bfcb8b27.png
      Figure \(\PageIndex{1}\)
    2. clipboard_e41640950e0636d6feaab8c9e14409646.png
      Figure \(\PageIndex{2}\)
    3. clipboard_e23c409821666392ff69f91f342ad1cf4.png
      Figure \(\PageIndex{3}\)

    Activity \(\PageIndex{5}\)

    Consider the website Facebook as a graph where vertices are profiles and edges represent “friendship”.

    1. Should this graph be a directed graph? Why or why not?
    2. Is this graph simple? complete? Justify your answers.
    3. What does the degree of a vertex represent?
    4. Could this graph have isolated vertices?
    5. Suppose the following graph is a subgraph of the Facebook graph.
    clipboard_eec4877384b5f37cb5166418c8c73881a.png
    Figure \(\PageIndex{4}\)
    1. What is the largest party one of these people could throw where each party-goer is Facebook friends with every other party-goer? Justify your answer.
    2. Assume all of the people in this graph live in the same geographic area. Which pair of non-friends are most likely to become friends in the future? Which pair of non-friends are least likely to become friends in the future? Justify your answers.

    This page titled 14.5: Activities was last modified on Tue, 01 Sep 2026 03:35:27 GMT and is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform.