HW #2 solutions (non-book problems)

1. Show that n³-n is a multiple of 6, for any integer n.

Answer. Write n = 6m + r, where r is one of 0,1,2,3,4,5.
Then n³-n = (6m+r)³ - (6m+r) = some multiple of six plus r³ - r.
Then we check r³-r for each possible r, getting 0,0,6,24,60,120, each of which is a multiple of six.

---

2. Let G be a connected graph and v a vertex of degree 1. Using the
vertex-based definition we came up for of connectedness, prove that
the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v...")

---

A. Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v of vertices v_1..v_n such that v_1=w, v_n=x,
and {v_i,v_{i+1}} is an edge for each i=1..n-1.

Since G is assumed connected, we know there exists such a chain
of vertices in G, call it (w_1..w_m). (So w_1=w, w_m=x.)
(If for all i, w_i is not v, then this chain is also in G\v,
but we have to deal with the possibility that some w_i=v.)

Let u be the unique vertex such that {u,v} in E_G (unique by the
assumption that degree(v)=1).

For each i such that w_i=v, the only possibility for w_{i-1},w_{i+1} are
that each is equal to u. (Note that i is not 1 or n, since w,x are not v.)
Remove w_i, w_{i+1} from the chain, so that the new, shorter chain
goes ...,w_{i-1},w_{i+2},... We need to be sure that this still
has each vertex adjacent to the next one:
{w_{i-1},w_{i+2}} = {u,w_{i+2}} = {w_{i+1},w_{i+2}} in E_G. Voila.

In this way, we have constructed a chain of vertices connecting w to x,
none of which are equal to v. So this new, shorter chain is in G\v.
Since w,x were any two vertices of G\v, this shows G\v is connected.

---

3. Let G be a graph and v a vertex of degree 1. Assume that the
deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself...")

---

A. Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself.

As in #2, let u be the unique element of V_G to which v is connected.
Note that u is not equal to v, so u is a vertex of G\v.

There are then two cases: u in V1, or u in V2, since V1 union V2 = V_(G\v).

Assume u in V1. Let V1' = V1 union {v}.
Then we claim that (V1', V2) is a decomposition of G.
There are several things to prove:
1. V1' union V2 = V_G
2. V1' intersect V2 = {}
3. For any vertex a in V1' and b in V2, {a,b} is not in E_G.
We take them in order.

1. V1' union V2 = {v} union V1 union V2 = {v} union V_{G\v} = V_G,
by the definition of V_{G\v} as V_G with only v ripped out.
Also, we know V1 union V2 = V_{G\v} by the assumption that
they form a decomposition of G\v.
2. We know V1 intersect V2 = {}, by the assumption that they form
a decomposition of G\v. So the only chance for V1' to
share an element with V2 is if v is in both. But since
V1 union V2 = V_{G\v} doesn't contain v, V2 doesn't.
So V1' intersect V2 is empty.
3. a is either in V1, or a=v. Since V1,V2 is a decomposition,
if a is in V1 then there is no b in V2 with {a,b} in E_G.
So the other case is a=v. But then the only b in V_G such that
{a,b} is in E_G is b=u. And u is in V1, by assumption.
Hence u is not in V2, since V1 intersect V2 = {}.
So there is no b in V2 such that {a,b} is in E_G.

The other case, u in V2 instead of V1, is exactly the same except
with "V1","V2" switched throughout the proof.

---

4. What's the relation between #2 and #3?

---

A. We proved (mostly) in class that a graph has a decomposition iff it
is not connected. In light of that, #2 is equivalent to the
contrapositive of #3.

G connected ===> G\v connected
has contrapositive
G\v disconnected ===> G disconnected
or equivalently
G\v has a nontrivial decomposition ===> G has a nontrivial decomposition