Math 137A Assignment #8
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Math 137A Assignment #8
Due: Friday, June 10th by midnight on GradeScope. Instructions: Please complete 10 questions .
1. Calculate κ(G) and κ′ (G) for the following graph.
2. If G is a 3-regular simple graph, prove that κ(G) = κ′ (G). Find the smallest such G with κ(G) = 1.
3. Prove that a simple graph is 2-connected if and only if for every ordered triple (x, y , z) of vertices, G has a path from x to z containing y .
4. Suppose G is a 3-regular simple graph with at most 10 vertices. Prove that if G is not 3-edge-connected, then G contains at triangle.
5. Let G be a 2-connected graph with n vertices and m edges. Let (G0 , G1 , . . . , Gk) be an ear decomposition of G. That is, each Gi is obtained from Gi−1 by adding a path between two vertices. Find a formula for k in terms of n and m.
6. Find a maximum flow from s to t in the following digraph (numbers listed are edge capacities). Prove your flow is maximum by finding a corresponding minimum cut.
|
• 10
6 |
5 |
|
• |
|
• |
3
|
||
3 10 t
7. In this question we extend the notion of an (s, t)-flow to one in which there are two sources s1 , s2 (so at both of these vertices we do not need that flow in equals flow out). Use the (single source) max-flow min-cut theorem to find a flow in the following network so that the net flow into t is maximum. For the curved/double arrows, the capacities are
25 and 3 in each direction respectively.
8. Suppose the baseball league1 currently has the following standings, where the last five columns represent the remaining games to be played between the team in row x and column y .
1 There are no ties in baseball.
|
Team |
Wins |
A B C D E |
|
A B C D E |
15 14 11 9 8 |
- 3 1 1 4 3 - 2 3 1 1 2 - 1 2 1 3 1 - 1 4 1 2 1 - |
Use the method discussed in the video to show that E has a path to finish in first place, but that if A beats C in one game, then E is eliminated.
9. Let d1 ≤ d2 ≤ · · · ≤ dn be the degree sequence of a simple graph G. Prove that G is connected if dk ≥ k for every k ≤ n − 1 − dn . Hint: If G is not connected, consider a component that omits some vertex of maximum degree .
10. Let G be a connected graph where each edge has an associated cost. A bottleneck spanning tree is a spanning tree where the maximum of the edge costs in the tree is as small as possible. Prove that any minimum spanning tree is a bottleneck spanning tree.
11. Let G be a simple planar graph with at least 11 vertices. Prove that the complement G of G is nonplanar. (The complement is defined with V (G) = V (G) and v , w adjacent in G if and only if v , w are non-adjacent in G.)
12. A graph G is said to be k - critical if χ(G) = k and for any proper subgraph H of G, χ(H) < k .
(a) Find all 2-critical and 3-critical graphs.
(b) Give an example of a 4-critical graph.
(c) Prove that if G is k-critical, then every vertex of G has degree at least k − 1.
(d) Prove that if G is k-critical, then G is 2-connected.
2022-06-07