▗▄▄▄▖▗▞▀▚▖▄▄▄▄  ▄    ■  ▗▞▀▜▌▄   ▄  ▄▄▄       ▗▄▖    ▗▖ ▄▄▄  
  █  ▐▛▀▀▘█ █ █ ▄ ▗▄▟▙▄▖▝▚▄▟▌█   █ █   █     ▐▌ ▐▌   ▗▖█   █ 
  █  ▝▚▄▄▖█   █ █   ▐▌        ▀▀▀█ ▀▄▄▄▀     ▐▌ ▐▌▄  ▐▌▀▄▄▄▀ 
  █             █   ▐▌       ▄   █           ▝▚▄▞▘▀▄▄▞▘      
                    ▐▌        ▀▀▀
$ From the definition of isomorphism, prove that `G cong H iff bar(G) cong bar(H)`.
Proof.

Suppose `G cong H`. Then, there exists a bijection `f: V(G) to V(H)` such that `uv in E(G) iff f(u)f(v) in E(H)`.

Because taking the complement of a graph does not change its vertex set, `f` is also a bijection from `V(bar(G)) to V(bar(H))`.

Suppose that `uv in E(bar(G))`. Then, `uv notin E(G)`. Therefore, `f(u)f(v) notin E(H)`, so `f(u)f(v) in E(bar(H))`. Now, suppose that `uv notin E(bar(G))`. Then, `uv in E(G)`. Therefore, `f(u)f(v) in E(H)`, so `f(u)f(v) notin E(bar(H))`. Thus `G cong H implies bar(G) cong bar(H)`.

Now, suppose that `bar(G) cong bar(H)`. Because `G cong H implies bar(G) cong bar(H)`, as we've just shown, `bar(G) cong bar(H) implies bar(bar(G)) cong bar(bar(H))`. For all graphs `X`, `bar(bar(X)) = X`, so `bar(G) cong bar(H) implies G cong H`.

Thus, `G cong H iff bar(G) cong bar(H)`. q.e.d

$ Prove or disprove: If every vertex of a simple graph `G` has degree 2, then `G` is a cycle.

False. A simple disconnected graph `G` with every component a triangle is not a cycle.

$ Prove that a graph with more than six vertices of odd degree cannot be decomposed into three paths.
Proof.

Suppose graph `G` with `n > 6` vertices of odd degree can be decomposed into three paths `P_1, P_2, P_3`. In any path, the two end-points have degree 1(odd) and all internal vertices have degree 2(even).

When we combine the paths, the degree of any vertex `v in G` equals the sum of its degrees across all paths containing `v`. Since even + even = even and even + odd = odd, vertex `v` has an odd degree in `G` if and only if `v` is an endpoint in an odd number of paths.

Since there are three paths with two endpoints each, there are at most 6 endpoint positions. Therefore, at most 6 vertices can be endpoints in an odd number of paths. Thus `n leq 6` and this contradicts our initial assumption that `n > 6`.

Therefore, a graph with more than six vertices of odd degree cannot be decomposed into three paths.

q.e.d
$ Prove or disprove: The complement of a simple disconnected graph must be connected.
Proof.

Let `G` be a simple disconnected graph. Since `G` is disconnected, we can partition `V(G)` into non-empty, disjoint sets `V_1` and `V_2` such that no edge in `E(G)` connects `V_1 to V_2`.

Let `u,v in V(G)` be arbitrary vertices.

If `u in V_1` and `v in V_2` (or vice versa), then `uv notin E(G)`, so `uv in E(bar(G))`.

If `u,v` are both in `V_1` (or both in `V_2`), pick any `w` from the other part. Then `uw in E(bar(G))` and `wv in E(bar(G))`, giving path `u - w - v`.

Since any two vertices in `bar(G)` are connected by a path, `bar(G)` is connected.

q.e.d
$ Prove that removing opposite corner squares from an 8-by-8 checkerborard leaves a subboard that cannot be partitioned into 1-by-2 and 2-by-1 rectangles. Using the same argument, make a general statement about all bipartite graphs

[...under development]

$ Prove that the petersen graph has not cycle of length 7.

[...under development]

$ Let G be a graph with girth 5. Prove that if every vertex of `G` has degree at least `k`, then `G` has a t least `k^2 + 1` vertices. For `k = 2` and `k = 3`, find one such graph with exactly `k^2 + 1` vertices.

[...under development]

$ The Odd Graph `O_k`. The vertices of graph `O_k` are the k-element subsets of `{1,2,...,2k+1`. Tow vertices are adjacent if and only if they are disjoint sets. Thus `O_2` is the Pertersen graph. Prove that the girth of `O_k` is `6` if `k ge 3`.

[...under development]

$ Prove that every set of six people contains (at least) three mutual acquantancies of three mutual strangers.

[...under development]

$ Prove that a self-complementary graph with `n` vertices exists if and only if `n` or `n-1` is divisible by `4`. (Hint: When `n` is divisible by 4, generalize the structure of `P_4` by splitting the vertices into four groups. For `n mod 1` mod `4`. add one vertex to the graph constructted for `n - 1`.)

[...under development]