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.)

  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.)