- #1
roadrunner
- 101
- 0
So my course is just getting further and further above my head. I got most of them but I'm stuck on these 3 and have no idea how to start them.
This is due friday so hopefully I can get input before that! :)
1) Let G be a (2k + 1)-regular graph, and assume that G - S is still connected
for any set S of edges with |S| < 2k. Prove that G has a perfect matching.
I know that there must be even number of vertices
I know that G-S means that every vertice is still guaranteed to have at least degree 2 (since it starts with degree 2k+1 and if all all of the edges is S were connected to a vertice then it will have 2k-1 less. )
But I don't know where to go from there or if that is even helpful?!
5) Let G be a simple graph with no isolated vertex. Assuming every vertex of G
has degree < d, show that a'(G) >= V (G)/(d + 1).
a' is the size of the maximum matching
12) Let G be a k-regular graph with an even number of vertices, and assume that
for any two odd cycles C1,C2 in G either V (C1) union V (C2) does not equal null ;, or there is an edge with one
end in V (C1) and the other in V (C2). Prove that G has a perfect matching. (Hint: suppose
for a contradiction that this is false, and choose a set X in V (G) of so that odd(G-X)>-|X|
is maximum and subject to this X is as large as possible, as in the proof of Tutte's theorem).
This is due friday so hopefully I can get input before that! :)
1) Let G be a (2k + 1)-regular graph, and assume that G - S is still connected
for any set S of edges with |S| < 2k. Prove that G has a perfect matching.
I know that there must be even number of vertices
I know that G-S means that every vertice is still guaranteed to have at least degree 2 (since it starts with degree 2k+1 and if all all of the edges is S were connected to a vertice then it will have 2k-1 less. )
But I don't know where to go from there or if that is even helpful?!
5) Let G be a simple graph with no isolated vertex. Assuming every vertex of G
has degree < d, show that a'(G) >= V (G)/(d + 1).
a' is the size of the maximum matching
12) Let G be a k-regular graph with an even number of vertices, and assume that
for any two odd cycles C1,C2 in G either V (C1) union V (C2) does not equal null ;, or there is an edge with one
end in V (C1) and the other in V (C2). Prove that G has a perfect matching. (Hint: suppose
for a contradiction that this is false, and choose a set X in V (G) of so that odd(G-X)>-|X|
is maximum and subject to this X is as large as possible, as in the proof of Tutte's theorem).