# MCS-236 Homework 3

This set is due Monday, September 30.

As always, please stop by my office if you'd like help understanding a problem, setting up a proof, or in writing up a proof.

1. (Similar to exercise 1.2.17) Let Gn be the graph whose vertices are permuations of 1, ..., n, with two permutations adjacent if the differ by interchanging any pair of entries. (See diagram, but add 3 more edges connecting opposite corners of the hexagon.)
• Prove Gn is connected.
Hints: One way to proceed is as follows: Define d(u,v) be the number of position in which two vertices u and v differ. Use induction to prove that for all l (at least 0), and for all vertices u and v if d(u,v)=l there is a path from u to v in Gn.

Your goal in the induction step is then to prove that from u there exists a way to go one step towards v. I.e., to show that there is a u' adjacent to u so that d(u',v) is less than d(u,v), then use induction.

• For what values of n is Gn Eulerian? Prove your answer. (Hint: First give an exact formula for the number of neighbors of any vertex u as a function of n.

2. Do exercise 1.2.20. Let v be a cut-vertex of a simple graph G. Prove G-complement minus v is connected.

3. Do exercise 1.2.26. Prove that a graph G is bipartite if and only if every subgraph H of G has an independent set consisting of at least half of V(H).

This is an "if and only if" statement: If A is "G is bipartite" and B is "every subgraph H of G has an (large) independent set,", your goal is to show A if and only if B. I found that the easiest way to prove this was:

1. If A then B: Suppose G is bipartite, and let H be any subgraph of G... (Show H has a large independent set.)
2. If not A then not B: Suppose G is non-bipartite... (Find a subgraph H that can't have a large independent set.)
(I originally asigned 1.2.25. Feel free to do it if you prefer.)