
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 Gx1x2...xk is connected
3. Prove that every kconnected graph must contain an edge e such that Ge is kconnected, unless G has a vertex of degree k.