Applied graph theory

Applied graph theory, Math 2400, dsg

Homework 1, 
Please see the handout for proper format of homework submissions. This assignment is
worth 20 points, and the value of each question is in square brackets on the left.
[4] 1. How many simple graphs on 4 (unlabelled) vertices have precisely 3 edges? How
many simple graphs are there on 4 labelled vertices? Justify your answers by showing all
such graphs.
[4] 2. List all multigraphs on 4 labelled vertices that have 3 edges. How many are there?
[4] 3. Are the two following graphs isomorphic? (The first is called the Petersen graph.)
If so, label both graphs with the same set of labels that reveals the isomorphism between
0
the vertex sets (verify by checking all 12 = 45 pairs!) If not, exhibit a property of one
graph that the other fails to have.
Figure 1: The Petersen graph, and another graph—are they isomorphic?.
[4] 4. Are the following degree sequences graphic? If so, draw one graph with that
degree sequence; if not, show why.
(a) (6,3,3,3,3,2)
(b) (3,3,3,3,3,3)
(c) (4,2,2,2,2,1,0,0,0)
(d) (0,1,2,3,4,5,6,7)
[4] 5 Let G denote a simple graph on n ≥ 2 vertices. Prove that two vertices have the
same degree.

    • 10 years ago
    100% correct answer A++ work Guaranteed the best Tutorial
    NOT RATED

    Purchase the answer to view it

    blurred-text
    • attachment
      graph1.docx
    • attachment
      graph_2.docx