Installing Macaulay in Windows 10 using Linux Subsystem

This was really hard for me since I know almost nothing about Linux, but it can be done.

You can use the steps here, but you need to know what you're doing, or it will be trial and error until you get it. Also from what I know and expect, you'll be unable to use the Synaptic Package Manager so everything must be done from the terminal.

The first step is installing the Ubuntu terminal from the Windows Store, and activating it, as here. Note that you'll need to have the developer mode activated.
Then, you'll need to open it to finish its installation, and set up a user and password.

The next step, from the terminal is to add the line

deb http://www.math.uiuc.edu/Macaulay2/Repositories/Ubuntu XXXX main

to the file /etc/apt/sources.list, replacing XXXX by the corresponding word, and if, like me, you have no idea how to do that, then you first have to check the Ubuntu version from the terminal with the comand lsb_release -a. 

In my case, I have 18.04 so I must replace XXXX by bionic.

Now, to add that line to the sources.list file I wrote the following in the terminal, just like it said here:

echo "deb http://www.math.uiuc.edu/Macaulay2/Repositories/Ubuntu XXXX main" | sudo tee -a /etc/apt/sources.list

I didn't use gedit because I don't know if I can install it and make it work from the terminal (It's a text editor for ubuntu). I think it can be done following the instructions for Macaulay with emacs but when I tried that way something like a year ago it didn't work. But then I didn't know how to use apt so that is likely to be the reason. This way it doesn't require to install anything else. The following is to add the key, but it's tricky. You have to download de key, and get to that folder. If you don't know the syntax for the directories in Ubuntu it may be confusing. You must download the key, and then you can move it to C://, use the command cd /mnt/c/ to get to C:// and then use the command in the instructions:

sudo apt-key add Macaulay2-key

From then on, everything should be like in the instructions: Just use the commands 

sudo apt-get update -q 

sudo apt-get install -y -q macaulay2

then wait for it to install and you'll be done in no time. You can open Macaulay from the terminal using M2.

A few exercises about Associated Primes.

I'm trying to learn about Stanley-Reisner rings, and these are some exercises previous to the theory. These are taken from Villarreal's book: Graphs, Rings and Polyhedra.

There will be more.

Exercise 1.

Let $I$ be an ideal of a ring $R$. Prove that $\rad I=I$ if and only if for any $x\in R$ such that $x^2\in I$ we have $x\in I$.

Proof.

First suppose $I$ is a radical ideal. Let $x\in R$ be such that $x^2\in I$. Then $x\in \rad I=$. Conversely, suppose that for any $x\in R$ such that $x^2\in I$ we have $x\in I$. We want to prove that if $y^n\in I$ for some $n$ then $y\in I$, and we'll try using induction. For $n=1,2$ the result already holds. Take $n>2$, suppose that $y^k\in I\Rightarrow y\in I$ for $k<n$ and suppose $y^n\in I$. If $n$ is even, then by the $k=2$ case it means that $y^{\frac{n}{2}}\in I$ from what by induction hypothesis $y\in I$. If $n=2j+1$ is odd then $y^{2j+1}\in I$. So $y^{2j+2}\in I$ and by the $k=2$ case we get $y^{j+1}\in I$. Then, by induction hypothesis $y\in I$.

Exercise 2.

Let $I_1,\dots,I_n,P$ be ideals of a ring $R$ with $P$ prime. Suppose that

$$J=\bigcap_{i=1}^n I_i\subseteq P.$$

Prove that there is some $i\in \{1,\dots,n\}$ such that $I_i\subseteq P$. In particular, if $\bigcap_{i=1}^n I_i=P$ then prove that there is some $i$ such that $I_i=P$.

Proof.

Suppose not. Then, for each $i$ there are elements $f_i\in I_i$ such that $f_i\notin P$. Then $f_1\cdots f_n\in J\subseteq P$. Since $P$ is prime and $f_1\notin P$ then $f_2\cdots f_n\in P$. Since $f_2\notin P$ then $f_3\cdots f_n\in P$. Thus, $f_n\in P$, a contradiction. So there is some $i$ such that $I_i\subseteq P$.

For the second case, consider, by a permutation, that $I_n\subseteq P$. Let $x\in P$, then $x\in J$, so $x\in I_n$, therefore $I_n=P$.

Exercise 3.

Let $R$ be a ring and $P$ a proper ideal of $R$. If every element of $R/P$ is nilpotent or invertible, prove that $P$ is a primary ideal. 

Proof.

Suppose $fg\in P$. Then $fg+P=(f+P)(g+P)=0$. Suppose $f+P$ is invertible. Then $g+P=0$, and $g\in P$. Now suppose $f+P$ is not invertible. Then $f+P$ is nilpotent and there is some $n$ such that $f^n+P=0$, i.e. $f^n\in P$. Therefore, $P$ is primary.

Exercise 4.

Let $R$ be a ring and $I$ be an ideal. If $x\in R-I$ then there is an exact sequence of $R-$modules

$$0\to R/(I:x)\stackrel{\psi}{\to} R/I\stackrel{\phi}{\to} R/(I,x)\to 0$$

where $\psi(r+(I:x))=xr+I$ and $\phi(x+I)=x+(I,x)$.

Proof.

First we'll prove that $\psi$ is injective. Suppose $\psi(r+(I:x))=xr+I=0$. Then $xr\in I$ so that $r\in (I:x)$ and $r+(I:x)=0$.

Now we'll prove that $\phi$ is a well defined surjective map. It's just that since $I\subseteq (I,x)$, then the canonical map $\pi:R\to R/(I,x)$ factors through $I$. And for $r+(I,x)\in R/(I,x)$ just take $r+I\in R/I$ and we're done, for $\phi(r+I)=r+(I,x)$.

Now we'll prove that $\im \psi=\ker \phi$.

Take $r+I\in R/I$. Then

$r+(I,x)=0$ iff $r\in (I,x)$, iff there exist $a\in I,b\in R$ such that $r=a+bx$, but this occurs iff $r+I=a+bx+I=bx+I\in \im \psi$. So $\im\psi=\ker\phi$ and the sequence is exact.

From now, a map will be a morphism in a corresponding category (Only if it is not ambiguous, in which case we'll talk about the corresponding kind of morphism).

Exercise 5 (Localization defines a covariant functor).

If $\phi:M\to N$ is a map of $R-$modules then there is an induced map of $S^{-1}R-$módules:

$$S^{-1}\phi:S^{-1}M\to S^{-1}N$$

given by $\frac{m}{s}\mapsto \frac{\phi(m)}{s}$.

Proof.

$S^{-1}\phi$ is a well defined function. Indeed, $\frac{m}{s}=\frac{m'}{s'}$ implies $t(s'm-sm')=0$ for some $t\in S$, which implies $t(s'\phi(m)-s\phi(m'))=0$, which means $\frac{\phi(m)}{s}=\frac{\phi(m')}{s'}$.

Now, take Take $f=\frac{r_1}{s_1}\frac{m_1}{s_1'}+\frac{r_2}{s_2}\frac{m_2}{s_2'}\in S^{-1}M$. Then $$f=\frac{r_1s_2s_2'm_1+r_2s_1 s_1'm_2}{s_1s_1's_2s_2'}$$

and

$$S^{-1}\phi(f)=\frac{\phi(r_1s_2s_2'm_1+r_2s_1 s_1'm_2)}{s_1s_1's_2s_2'}=\frac{r_1s_2s_2'\phi(m_1)+r_2s_1 s_1'\phi(m_2)}{s_1s_1's_2s_2'}$$

which is clearly 

$$\frac{r_1}{s_1}S^{-1}\phi\left(\frac{m_1}{s_1'}\right)+\frac{r_2}{s_2}S^{-1}\phi\left(\frac{m_2}{s_2'}\right)$$

so $S^{-1}\phi$ is a map of $S^{-1}R-$modules.

Also note that $S^{-1}I_M=I_{S^{-1}M}$ and $S^{-1}(\phi)\circ S^{-1}(\psi)(\frac{m}{s})=\frac{\phi\circ\psi(m)}{s}=S^{-1}(\phi\circ\psi)$, so localization is a functor.

Exercise 6.

Following on the previous exercise, $S^{-1}(-)$ is an exact functor.

Proof.

Take an exact sequence

$$0\to L\stackrel{\psi}{\to} M\stackrel{\phi}{\to} N\to 0$$

Now, $S^{-1}\psi$ is injective.

Indeed, suppose $S^{-1}\psi(\frac{l}{s})=\frac{\psi(l)}{s}=0$. Then there is $t\in S$ such that $t\psi(l)=\psi(tl)=0$ so $tl=0$ thus $\frac{l}{s}=0$ and $S^{-1}\psi$ is injective.

Now, to prove $S^{-1}\phi$ is surjective, just notice that every $\frac{n}{s}\in S^{-1}N$ has the form $\frac{\phi(m)}{s}=S^{-1}\phi(\frac{m}{s})$ for some $m\in M$. Therefore $S^{-1\phi}$ is surjective.

Now we want to prove that $\ker S^{-1}\phi=\im S^{-1}\psi$.

Take $\frac{m}{s}\in S^{-1}M$. Then $S^{-1}\phi(\frac{m}{s})=\frac{\phi(m)}{s}=0$ iff there is some $t\in S$ such that $tm=0$, iff there is some $l\in L$ such that $\psi(l)=tm$, iff $S^{-1}\psi(\frac{l}{ts})=\frac{psi(l)}{ts}=\frac{tm}{ts}=\frac{m}{s}$, which is the desired result, that the induced sequence

$$0\to S^{-1}L\stackrel{S^{-1}\psi}{\to} S^{-1}M\stackrel{S^{-1}\phi}{\to} S^{-1}N\to 0$$

is exact, and $S^{-1}(-)$ is an exact functor.

Exercise 7.

If $M,N$ are $R-$modules then $\Ass(M\oplus N)=\Ass M\cup \Ass N$.

Proof.

Let $P=\Ann(m+n)\in\Ass(M\oplus N)$ for $m+n\neq 0$. Then $x\in P$ iff $xm=0$ and $xn=0$ iff $x\in \Ann(m)\cap\Ann(n)$, so $P=\Ann(m)\cap \Ann(n)$. By a previous exercise, $P=\Ann(m)$ or $P=\Ann(n)$. Thus, $P\in \Ass(M)\cup \Ass(N)$.

Conversely if $P\in\Ass(M)\cup\Ass(N)$ then $P=\Ann(m)$ for some $m\in M\cup N$. Then since $m\in M\oplus N$, $P\in \Ass(M\oplus N)$.

Therefore, $\Ass(M\oplus N)=\Ass(M)\cup \Ass(N)$.

Exercise 8.

If $\rad Q$ is maximal then $Q$ is primary.

Proof.

Suppose $ab\in Q$ with $b^n\notin Q$ for every $n$. Then $b\notin \rad Q$. Since $\rad Q$ is maximal then $\rad Q+\langle b\rangle=R$, so there exists $c\in R$ and $q\in\rad Q$ such that $q+cb=1$. Since $q\in\rad Q$ there exists some $n$ such that $q^n\in Q$. So $(q+cb)^n=q^n+rb=1$ where $r\in R$. But $q^n\in Q$, so $a(q^n+rb)=aq^n+rab=a\in Q$.

Therefore $Q$ is primary.

Exercise 9 (Lemma).

If $0\to M'\stackrel{\phi}{\to} M\stackrel{\psi}{\to} M''\to 0$ is an exact sequence of $R-$modules then

$$\Ass(M)\subseteq \Ass M'\cup \Ass M''.$$

Proof.

Let $P\in\Ass M$. Then there is a monomorphism $\rho:R/P\to M$. Set $N=\rho(M)$. Then $\rho|_{N}$ is an isomorphism, thus for every $m\in N-0$ we have $\Ann(m)=P$\footnote{This is because for $m\in N-0$, $xm=0$ iff $x\rho^{-1}(m)=0$ iff $x\in P$, because $P$ is prime and $\rho|_{N}^{-1}(m)\neq 0$.}.

Set $N'=\phi(M')$ and suppose $N'\cap N\neq 0$. Then, take $0\neq s\in N'\cap N$, then, since $\Ann(s)=P$, and $\phi$ is a monomorphism, $\Ann(\phi|_{M}^{-1}(s))=P$, thus $P\in \Ass M'$. Now, suppose $N\cap N'=0$ so $N\cap \ker\psi=0$, thus the composition $\overline{\rho}=\pi\circ\rho:R/P\to M/\ker\psi\cong M''$ is also a monomorphism ($\pi$ is the canonical map), therefore $P\in\Ass M''$. 

Diameter of random graph.

Proposition. For a fixed $p\in (0,1)$ almost every graph in $G(n,p)$ has diameter $2$.

Proof.  Note first that a graph $G$ in $G(n,p)$ has diameter $1$ iff it's a complete graph in $n$ vertices, so that $P(\diam G=1)=p^{\binom{n}{2}}\to 0$ when $n\to\infty$. So, if we prove that almost every graph in $G(n,p)$ has diameter $\leq 2$ we're done.

Suppose a graph $G$ has diameter $>2$. Then there are two vertices $u,v$ such that $d(u,v)>2$, so that $N(u)\cap N(v)=\varnothing$. Conversely, if this last property holds for some graph, the graph must indeed have diameter $>2$. So, to prove that almost every graph in $G(n,p)$ has diameter $2$ we need to prove that almost every graph in $G(n,p)$ does not have vertices with disjoint neighborhoods. Consider the following random variable on $G(n,p)$:

$$X(G)=|S(G)|$$

where $S(G)=\{(u,v)\in V(G)\times V(G)\mid N(u)\cap N(v)=\varnothing\}$, so that a graph in $G(n,p)$ will have diameter $\leq 2$ iff $X(G)=0$.

By Markov's inequality,
$$P(X\geq 1)\leq E(X),$$
so we're left to prove that $\lim_{n\to\infty} E(X)=0$.
Now, $E(X)=\sum_{G\in G(n,p)}P(G)X(G)$.

For a given vertex $x\in V(G)$, the probability of it being adjacent to both vertices $u,v$ is $p^2$, so the probability of $x\notin N(u)\cap N(v)$ is $1-p^2$, so $P(N(u)\cap N(v)=\varnothing)=(1-p^2)^{n-2}$. Also $P(uv\notin E(G))=1-p$.

So,
$$E(X)=\binom{n}{2} (1-p)(1-p^2)^{n-2}.$$
Letting $n\to\infty$, since $|1-p^2|<1$, $(1-p^2)^{n-2}\to 0$ and $\lim_{n\to \infty} E(X)=0$.

Thus $\lim_{p\to \infty} P(X\geq 1)=0$, so that almost every graph in $G(n,p)$ has no such vertices $u,v$, and therefore almost every graph in $G(n,p)$ has diameter $\leq 2$, and still almost every such graph has diameter $2$.

A graph with at most one vertex of degree less than 3 has a subdivision of $K_4$

This is about a problem in the Bondy and Murty's book on Graph Theory.

Let $G$ be a nontrivial simple graph with $\delta(G)\geq 3$ or a vertex $v\in V(G)$ such that $\delta(G-v)\geq 3$. Then $G$ has a subdivision of $K_4$.

This is also about a question made by me in math.stackexchange about a case when the graph was $2-$connected but not $3-$connected. My original reasoning was as follows:

There are some remarks to do: First, we can reduce the cases to the first one: $\delta(G)\geq 3$. If $d(v)<3$ we can take an edge $e$ such that $v\in e$ and by induction on $|G|$, $G/e$ has a subdivision of $K_4$, so $G$ also has one. We can also suppose $G$ is connected since we can also use induction on its components. We can also suppose $G$ is planar since both $K_5$ and $K_{3,3}$ have subdivisions of $K_4$.

The first thing I tried to do was check (as stated above) that we could suppose $G$ was planar, but my last attempt was checking the connectedness of the graph as follows:

If $G$ is connected, has $\delta(G)\geq 3$ and is not $2-$connected, then take a cut-vertex $v$ and a component $C$ of $G-v$. Then the induced subgraph of $C\cup v$ has at most one vertex of degree $<3$ (the cut-vertex), and by induction we're done. So we can suppose $G$ is $2-$connected. If we can reduce the case to one on which $G$ is $3-$connected then any $3$ vertices are in a common cycle, and then we can apply the Fan Lemma or Menger Theorem appropiately to get the subdivision of $K_4$ (It will be a cycle of length at least $3$ not covering all the vertices and a $3-$fan from one of the remaining vertices to that cycle).

But as Misha Lavrov comments there, there is a flaw in the first paragraph of the attempt, which is shown in the following graph.

When contracting an edge incident to the red vertex it becomes the following graph:

which has two vertices of degree two. This can still be solved and the reasoning to do it will be shown next.

Using the Misha's answer and my own remarks, and ignoring the fan-lemma we have the following proof:

Proof. Suppose first that $G$ is not $3-$connected. For such a graph, we'll prove the result by induction on $n=|G|$. For $n=4$ the result is trivial ($G$ must be $K_4$), so we can suppose that $n>1$ and that any graph with less than $n$ vertices and at most one vertex of degree $<3$ contains a subdivision of $K_4$. Now, if, in fact, $G$ is not connected, then its connected components all have at most a vertex of degree $<3$. By induction hypothesis, each of them, besides a possibly trivial one (on which case the rest of them would have minimum degree $\geq 3$) contains a subdivision of $K_4$ so $G$ too. Let's now suppose $G$ is connected, but has a cut-vertex $v$. Let $C$ be a connected component of $G-v$ with no vertex of $G$ with degree $\leq 2$ (this is how we solve the problem mentioned above). Then $G[C\cup v]$ has at most one vertex of degree $2$ ($v$ is the only candidate). By induction hypothesis, $G[C\cup v]$ contains a subdivision of $K_4$; so does $G$, then. 

Now suppose $G$ is $2-$connected but contains a separating set of minimum size $S$ with two vertices. Take $S=\{v,w\}$ in such a way that a component $C$, with no vertices of $G$ with degree $\leq 2$, of minimum size of $G-S$ is as smallest as possible.  

This means that both $v$ and $w$ have two adjacent vertices in $C$. Indeed, if $v$ (resp. $w$) has only one adjacent vertex $v'$ in $C$, then $\{v',w\}$ is another separating set in $G$, with a component being $C'=C-v'$. Also, $C'\neq \varnothing$, in such a case it would happen that $C=\{v'\}$ and $d(v')=2$, a contradiction.

Furthermore, since $v,w$ both have adjacent vertices in any other component of $G-S$, then there exists a $v-w-$path, say, $\gamma$ not meeting $C$.

Take a new graph $G'$ defined as follows: 

$$V(G')=V(C)\cup S,$$

$$E(G')=E(C)\cup E(S,C)\cup \{vw\}.$$

By the choice of $C$, again, $v,w$ have each one at least two edges to $C$, and the edge $vw$, adding $3$ to both degrees, so $d(v),d(w)\geq 3$. Then $\delta(G')\geq 3$ (Since the only changing degrees are the ones of $v,w$). By induction hypothesis, $G'$ contains a subdivision of $K_4$. If $vw\in E(G)$ we're done. If this subdivision uses $vw$ and $vw\notin E(G)$, then, in $G$, replace $vw$ by $\gamma$. It'll still be a subdivision of $K_4$. Therefore, every non-$3-$connected graph with at most one vertex of degree $\leq 2$ has a subdivision of $K_4$.

Now suppose $G$ is $3-$connected. We know, by Tutte's wheel theorem that $K_4$ is a minor of $G$, but we're looking for $K_4$ as a topological minor which is not the same. We'll work as follows: Take a cycle $\zeta$ of $G$ of minimum length, in such a way it's an induced cycle. Since $G$ is $3-$connected, then $G\neq \zeta$ and since $\zeta$ is induced, there is $v\in V(G)-V(\zeta)$. Also $\delta(G)\geq 3$, thus $d(v)\geq 3$. Since $N(v)$ separates $v$ fron $\zeta$, then by Menger's theorem there exist at least three disjoint $v-\zeta-$paths. Three of them, along with $\zeta$, make a subdivision of $K_4$.

Highly connected subgraph of a finite graph

In the article Forcing highly connected subgraphs from Maya Jakobine Stein there is a statement about a theorem of Mader which guarantees the existence of highly connected subgraphs of a given graph with a high minimum degree. Then a well known theorem of Mader which guarantees the existence given a high average degree is stated.

Theorem 1.  Any finite graph $G$ of average degree at least $4k$ has a  $(k+1)-$connected subgraph.

A result of the article is the following:

Theorem 2. Let $k\in\bN$ and let $G$ be a graph such that each vertex has degree at least $2k$ and each end has edge-degree at least $2k$. Then $G$ has a $(k + 1)-$edge connected region.

Theorem 1 doesn't guarantee by itself the existence of such a subgraph only given a minimum degree of $2k$ even in the finite case. The source of the theorem, which, unfortunately for me, is in German, may have such a result, but fortunately a simple proof of the following proposition follows from the steps used by Stein to prove Theorem 2.

Proposition 1. Let $k\in\bN$ and let $G$ be a finite graph with minimum degree $\delta(G)=2k$. Then $G$ has a $(k + 1)-$edge connected subgraph.

To understand a bit of Stein's proof, we have to know some concepts, like ray, end, region, boundary, and to adapt the proof to our finite case we must make sure none of those concepts are relevant for the finite case.

So, given a graph $G$ and a subgraph $H$, the boundary of $H$ is just the set $N(G-H)$ of all vertices of $G$ adjacent to some vertex in $G-H$. A region is a connected induced subgraph with finite boundary. An infinite path starting at some vertex is called a ray, and the ends are the equivalence classes of rays given a specific equivalence relation for them. The edge-degree of an end is the maximum cardinality of a set of edge-disjoint rays in it. So, indeed, since a finite graph has no rays, then it has no ends, and the corresponding hypothesis becomes a void one for the finite case. Also in a finite graph the boundary of any subgraph is obviously finite, so a region in a finite graph is just an induced subgraph.

With this we can say that the same proof should work in the finite case, but we also should be able to make it into a simpler proof. First, the proof is based on the following lemma:

Lemma. Let $D\neq \varnothing$ be a region of a graph $G$ so that $|E(D, G − D)| < m$ and so that $|E(D' , G − D')| ≥ m$ for every non-empty region $D' \subseteq D − \partial D$ of $G$. Then there is an inclusion-minimal region $H \subseteq  D$ with $|E(H, G − H)| < m$ and $H\neq \varnothing$.

The lemma is used to find a minimal region $C$ such that $|E(C, G − C)| < 2k$. But this lemma is just a big nuke for our finite case: If $G$ is not $(k+1)-$edge connected such a set $C$ exists: Take a minimum separating set $S$ of $G$ with $k$ edges, and a component $H$ of $G-S$. Such a component is a choice for the set $C$, and a good one since $|E(H,G-H)\leq k<2k$. The existence of a minimal one is also immediate: Any finite poset has a minimal element. Even more, we can take one of minimum size. So, for the following proof, which is in fact the last paragraph of the proof in the article (with a few more details), this set will be called $H$.

Proof of Proposition 1. Let $H$ be as in the comments above. We claim that $H$ is $(k+1)-$edge connected. Indeed, if it were not, then $|H|\geq 2$ (If $|H|=1$ then $V(H)=\{v\}$ for some $v\in V(G)$ and since $d(v)\geq 2k$, then $|E(H,G-H)|=d(v)\geq 2k$). Furthermore, $H$ has a minimum separating set $K'$ with $|K'|\leq k$. Then $H-K'$ has at least two components, say, $H',H''\subsetneq H$. If $$|E(H,G-H)\cap E(H',G'-H')|> \frac{E(H,G-H)}{2}$$
then $$|E(H'',G-H'')\cap E(H,G-H)|\leq \frac{E(H,G-H)}{2}< k.$$

So, given that, the following holds
$$E(H'',G-H'')\leq |E(H'',G-H'')\cap E(H,G-H)|+|K'|<2k$$
otherwise, if $|E(H,G-H)\cap E(H',G'-H')|\leq \frac{E(H,G-H)}{2}<2k$
then
$$E(H',G-H')\leq |E(H',G-H')\cap E(H,G-H)|+|K'|<2k.$$
Both cases contradict the minimality of $H$. Therefore, $H$ is $(k+1)-$edge connected.

Exercises on graph theory

Just some exercises of Bondy's and Murty's book. I also added some from Trudeau's book and Bollobás book.

Exercise 1. Let $G$ be a simple graph. Then $||G||\leq \binom{|G|}{2}$ where $|G|:=|V(G)|$ and $||G||:=|E(G)|$. Determine when equality holds.
Proof. First, the cardinality of the set of unordered pairs of a set $V$ is bounded by $\binom{|V|}{2}$, from which the first result follows. Now, a graph $G$ is complete iff it has exactly $\binom{|G|}{2}$ edges. Indeed, $G$ is complete if and only if every unordered pair ${u,v}$ of elements of $V(G)$ is in $E(G)$, if and only if there are $\binom{|G|}{2}$ of them.

Exercise 2. Every path is bipartite and a cycle is bipartite if and only if its length is even.
Proof. Let $G$ be a path and $n=|G|$. Partition $V=V(G)=\{v_1,\dots,v_n\}$ in the two sets $V_1=\{v_i\in V\mid i\text{ is odd.}\}$ and $V_0=\{v_i\in V\mid i\text{ is even.}\}$. Since every path in $G$ has the form $\{v_i,v_{i+1}\}$, and $i\not\equiv i+1\mod 2$ for every $i$, then the partition is adecuate for $G$ to be bipartite.

Now suppose $G$ is a cycle with even length. Then $n$ is also even. The partition given before still works so $G$ is bipartite. Now suppose that $G$ has odd length. If $V_1,V_2$ were a 'bipartition' of $V(G)$, then, renaming $V_1$ and $V_2$ appropiately we can suppose that $v_1\in V_1$. Then, since $V_1,V_2$ make a bipartition of $G$, the vertices adjacent to $v_1$, say, $v_{2},v_{n}$, must be in $V_2$. By applying the same reasoning repeatedly (starting with $v_2$ instead of $v_1$, in an ascending way) we conclude that $v_j\in V_1$ for every $j\equiv 1\mod 2$ and $v_j\in V_2$ for every $j\equiv 0\mod 2$. But applying the same reasoning (starting with $v_n$ in a descending way) we conclude that $v_j\in V_2$ for every $j\equiv n\equiv 1\mod 2$ and $v_j\in V_1$ for every $j\equiv 0\mod 2$. It follows that $V_1=V_2=V(G)$, a contradiction.

Exercise 3. Show that for any graph $G$, $\delta(G)\leq d(G)\leq \Delta(G)$, where $\delta(G),d(G),\Delta(G)$ denote the minimum, average, and maximum value between the degrees of the vertices of $G$ respectively.
Proof. For any set $A\subseteq \mathbb{Z}$, $\min A\leq \mu A\leq \max A$, where $\mu(A)$ denotes the average of the elements of $A$. So just take $A$ as the set of the degrees of the vertices of $G$.

Exercise 4.  Let $G$ be a graph. Then $G$ or $\overline{G}$ is connected.

Proof. Let's suppose $G$ is not connected and partition $G$ in it's more than one connected components, i.e. the partition associated to the equivalence relation $v\sim v'$ iff $v=v'$ or there is a path $v\leadsto v'$. Take two vertices $v,v'$. If they are in different connected components, then there is a path $v\leadsto v'$ in $\overline{G}$. If they are in the same one, take other vertex $w$ in another connected component. Then there are two paths $v\leadsto w,w\leadsto v'$. The composite path is a path $v\leadsto v'$. So, anyway, there is a path $v\leadsto v'$, thus $\overline{G}$ is connected.

Exercise 5. The graph $C_5$ is the only self-complementary cyclic graph.

Proof. If $C_5=[v_1,v_2,v_3,v_4,v_5,v_1]$ then $\overline{C}_5=[v_1,v_3,v_5,v_2,v_4,v_1]\cong C_5$, so $C_5$ is self-complementary. Furthermore, since the degree of all the vertices of $C_n$ is two, then if $n\neq 5$ the degree of the vertices of $\overline{C}_n$ is $n-3\neq 2$, so $\overline{C}_n$ can't be cyclic if $n\neq 5$.

Exercise 6. If $G$ is self-complementary then $|G|\equiv 0,1\mod 4$.

Proof. If $G$ is self-complementary then $||G||=||\overline{G}||$, so
$$\frac{|G|(|G|-1)}{2}=||K_{|G|}||=2||G||.$$
Then $|G|(|G|-1)=4||G||$. Suppose $|G|$ is odd. Then $|G|-1$ is even, and $\frac{4||G||}{|G|-1}=|G|$ is odd. This means that $4\mid |G|-1$. Otherwise, suppose $|G|$ is even. Then, by the same reasoning, $|G|-1=\frac{4||G||}{|G|}$ is odd, so $4\mid |G|$. The result follows.

An attempt to find the homology groups of $\bR P^n$ without using cellular homology

The homology groups of $P^n:=\bR P^n$ can be easily computed using cellular homology.
Here is an attempt to compute them by induction using the long exact sequence of homology. We want to prove that $H_m(P^n)=\mathbb{Z_2}$ for $m<n$ odd, $\mathbb{Z}$ for $m=0$, $0$ for $m$ even and $\mathbb{Z}$ if $m=n$ is odd. The case $n=2$ has already been proven here and $P^1\cong S^1$. My attempt goes like this:

 Let first $n>1$ be odd, and let's suppose for every $k<n$ the homology groups are as stated above. Then, using the fact that $P^{n-1}\subseteq P^n$ (As the projection of the points in $S^n$ which have a fixed coordinate null) and that $P^n/P^{n-1}\cong S^n$ we have a long exact sequence of (reduced) homology:
$$\cdots \to H_m(P^{n-1})\to H_m(P^n)\to H_m(S^n)\to H_{m-1}(P^{n-1})\to \cdots$$
and in particular, taking $m=n$ we have
$$\cdots \to H_n(P^{n-1})\to H_n(P^n)\to H_n(S^n)\to H_{n-1}(P^{n-1})\to \cdots$$
which gives us ($n-1$ is even), since $H_n(P^{n-1})=H_{n-1}(P^{n-1})=0$, the exact sequence
$$0\to H_n(P^n)\to \mathbb{Z}\to 0$$
and this gives an isomorphism between $\mathbb{Z}$ and $H_n(P^n)$.

Similarly, for $1\leq m<n$ with $m$ odd (If this case is possible), and since $H_m(P^{n-1})=\mathbb{Z}_2$ we have the exact sequence
$$0 \to \mathbb{Z}_2\to H_m(P^n)\to 0$$
and this gives an isomorphism between $\mathbb{Z}$ and $H_n(P^n)$.

Lastly, for $1<m<n$ even, and since $H_m(P^{n-1})=H_m(S^n)=0$ we have the exact sequence
$$0 \to H_m(P^n)\to 0$$
which means that $H_m(P^n)=0$.

So, for $n$ odd the job is done.

Similarly, take $n$ even and suppose that for every $k<n$ the homology groups are as stated above. Then take the long exact sequence:
$$\cdots \to H_m(P^{n-1})\to H_m(P^n)\to H_m(S^n)\to H_{m-1}(P^{n-1})\to \cdots$$
For $1\leq m< n-1$ odd we have $H_m(P^{n-1})=\mathbb{Z}_2$ and $H_m(S^n)=0$. Also $H_{m+1}(S^{n})=0$. So we have the exact sequence
$$0 \to H_m(P^{n-1})\to H_m(P^n)\to 0$$
which gives an isomorphism between $H_m(P^{n-1})$ and $H_m(P^n)$, so both of them are $\mathbb{Z}_2$.
For $1<m<n$ even we have, since $H_m(P^{n-1})=0$ and $H_m(S^n)=0$, the sequence
$$0\to H_m(P^n)\to 0$$
which results in $H_m(P^n)=0$.

The homology groups we haven't calculated yet are just the ones at the start of the long exact sequence, which is, since $H_n(P^{n-1})=0$,
$$0\to H_n(P^n)\to \mathbb{Z}\stackrel{\partial}{\to} \mathbb{Z}\to H_{n-1}(P^n)\to 0.$$

So what is left to prove is that the homomorphism $\partial$ is just multiplication by $2$. This is just a higher dimensional version of the problem here, and if can prove that, the result follows.