MATH 370 Graph Theory and Combinatorics Fall 2022 Problem Set 05
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 370
Graph Theory and Combinatorics
Fall 2022
Problem Set 05
1. (Exercise 5.1.10) Draw 11 non-isomorphic graphs of order 4.
2. Consider the following three graphs. Two of them are isomorphic. Find the pair that are isomorphic by identifying the appropriate one-to-one correspondence and explain why the third graph is not isomorphic.
3. Find a minimum weight spanning tree for each of the following graphs. Determine if the minimal spanning tree is unique.
|
7 |
|
|
|
7 |
7 12
4. An eighth bridge was built in K¨onigsberg in the 19th century as illustrated in the graph below. Is there an Euler path? Is so demonstrate the path. For an Euler path to exist where must an Euler path must start/end?
5. (Exercise 5.3.3) Consider the Petersen graph below. Does it have a Hamiltonian path? A Hamiltonian Cycle? In each case justify your answer.
d
6. In a tree, a pendant vertex is also known as a leaf. Suppose that T is a tree such that every vertex adjacent to a leaf has degree at least three. Prove there exists two leaves that share an adjacent vertex.
2022-11-15