Graph theory problems
Hello, everyone. I'm new in here and happy to know this great site.
I need help for several problems. If you know, please answer any of that. Thank you.
1. Prove that all stable matchings of a bipartite graph have the same size
2. Let G be a simple connected graph with minimum degree k
a) Prove that G has a path of length at least k
b) Prove that if x1, x2... xm is a longest path in G, then G-x1-x2-...-xk is connected
3. Prove that every k-connected graph must contain an edge e such that G-e is k-connected, unless G has a vertex of degree k.