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.
(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
- 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.
- Do exercise 1.2.20. Let v be a cut-vertex of a
simple graph G. Prove G-complement minus
v is connected.
- 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:
(I originally asigned 1.2.25. Feel free to do it if you prefer.)
- If A then B: Suppose G is bipartite, and let H be any subgraph of
G... (Show H has a large independent set.)
- If not A then not B: Suppose G is non-bipartite... (Find a
subgraph H that can't have a large independent set.)