Explore BrainMass

Explore BrainMass

    chromatic number of graph and adjacency matrix

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

    Please see attached questions.

    This is three questions.
    Question #1 - find the chromatic number of the graph.
    Question #2 - It might be supposed that if a graph has a large number of vertices and
    each vertex has a large degree, then the chromatic number would have to be large. Show
    that this conjecture is incorrect by constructing a graph with at least 12 vertices, each of
    degree at least 3, that is chromatic number 2.
    Need Attached Graph in editable format, i.e. xls, doc, etc.
    Question #3 - Find the adjacency matrix and adjacency list for the directed graph in the
    indicated exercise. Order the vertices according to alphabetical order.
    Let S - {1,2,4,8} and R = {(1,8), (2,4), (8,2), (4,1), (2,2), (8,1)} be the relation
    defined S. Draw the directed multigraph of this relation. Need Attached Graph in
    editable format, i.e. xls, doc, etc.

    © BrainMass Inc. brainmass.com March 4, 2021, 9:11 pm ad1c9bdddf


    Solution Preview

    See attached file for diagrams to go along with the solution.

    Answer: 1

    The chromatic number of a graph is the least number of colors required to do coloring of that graph or more clearly we can say that the chromatic number of a graph G is the smallest number of colors needed to color the vertices of G such that no two adjacent vertices share the same color.

    In the given graph, if we color vertex A with ...

    Solution Summary

    Basics of chromatic number of graph, adjacency matrix and list are described.