Explore BrainMass

Explore BrainMass


    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!


    Please select all the situations below that are POSSIBLE and do not mark those that are IMPOSSIBLE. Each list of numbers is a degree list (list of the degrees of all the vertices) of a graph. If there are extra restrictions - the graph is simple, or a tree, etc - it will be noted in the question.

    a. Graph, degrees: 1, 2, 3
    b. Tree, degrees: 0, 0, 1, 1, 2, 3, 3.
    c. Tree, degrees: 1, 1, 1, 1, 2, 4
    d. Simple graph, degrees: 1, 2, 3
    e. Simple graph, degrees: 0, 0, 0, 2.

    © BrainMass Inc. brainmass.com March 6, 2023, 2:29 pm ad1c9bdddf

    Solution Preview

    Before considering each graph in turn, the two definitions we need for simple graphs and trees, we state as:

    Definition: simple graph
    A graph is simple when it has no loops and no two distinct edges have exactly the same pair of ends.

    Definition: tree
    A tree is defined as a *connected* graph that contains no simple closed paths (i.e. it has no polygons as subgraphs).

    a. Graph, degrees: 1, 2, 3

    This is possible by construction. (Note: there ...

    Solution Summary

    This solution is comprised of a detailed explanation to graph appropriately.