Either draw a graph with the given specifications or explain why no such graph exists:
Full Binary Tree with height 4, 16 internal vertices.
No such graph exists, a full binary tree with height 4 has at most 24 terminal vertices and a full binary tree with 16 internal vertices has 17 terminal vertices ®
¬
.
Are these two graphs isomorphic? If so label their vertices so that the isomorphism is apparent. If not, list an isomorphic invariant that is violated.
Not isomorphic, any of the following isomorphic invariants are violated:
Cardinality of the edge sets are 8 and 7.
Score sequences: 2, 3, 3, 4, 4 and 2, 2, 3, 3, 4.
One vertex of degree 2 vs. two vertices of degree 2.
One vertex of degree 4 vs. two vertices of degree 4. And more…
Use either Kruskal's or Prim's Algorithm to find a minimum spanning tree. Specify the algorithm you use and show your work. What is the weight of your spanning tree?
