 # Graph Theory Questions

## Question

1. A graph G is k-extendable if|V (G)| ≥ 2k + 2 and for any k disjoint edges, there is a perfect matching containing them. Let G[A;B] be a bipartite graph with a perfect matching. If for any S ⊂ A, |N(S)| ≥ |S| + k, show that G is k-extendable.

2. Show that every 2-connected graph that has one perfect matching has at least two disjoint perfect matchings.

3. Show that a graph G is Eulerian if and only if there is a closed walk containing all the edges of G.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

3. A closed walk is a defined as a sequence of vertices where the first and last vertices are the same. This provides a connected graph which is Eulerian if and only if every vertex has even degree. If the graph contains a vertex of odd degree then the closed walk cannot contain all edges of G. Thus, a closed walk containing all edges of G shows that G only contains even degree vertices and is Eulerian....
\$15.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Mathematics - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.