Sure, here's a basic checklist. It would make for a very dry read to actually follow these to the letter, but maybe you should first try to write extremely formally, then see where it's reasonable to relax the writing without risk of misunderstanding or vagueness.
Preface. The high-level goal of formality is to make your proof closer to "machine-checkable". You want to allow people of a variety of different backgrounds, knowledge levels, abilities, and intuitions to be able to read your definitions, claims and proofs, understand what they say, and verify that they are correct.
Just as a computer cannot execute a program that is vague and skip steps, so it is difficult for a human to verify a proof with the same flaws.
However, a caveat is that mathematical formality is not perfectly aligned with conveying understanding. Notice I said "verify" above, not "understand". But even if the goal is to convey understanding, it is important to at least be able to formalize what one writes, since you want to convey to others the ability to formalize it.
- Define terminology and notation precisely. For example, this is informal:
each vertex gets a weight $w_v$ whenever it gets matched, and $W$ is
the total of all the weights.
This is formal:
the graph $G$ has a set of vertices $V$. For each vertex $v \in V$, the algorithm is given its weight $w_v$. For an algorithm $A$, let $S_A \subseteq V$ be the vertices matched by $A$. $S_A$ is a random variable depending on the random choices of $A$. Let $W_A = \mathbb{E} \sum_{v \in S_A} w_v$ where the expectation is over the randomness of $A$.
Why bury ourselves in so much notation? For one thing, notice that in the formal rewrite, we realized $W$ wasn't well-defined because it depended on the algorithm (and even its randomness), so we had to introduce and define notation to capture that. We had to introduce notation $S_A$, but it will come in handy later anyway.
Try not to feel frustrated or annoyed if things that sound simple take up a lot of space and require a lot of notation when written formally. Don't think of this as dirty work, think of it as a valuable part of the process to deeply understanding what you're writing.
Do not use a technical term if you have not defined it yet, and do not use nontechnical terms in a technical discussion or proof. For example, do not say "because $G$ is an expander, ..." as part of a step of a proof if a precise definition of expander has not yet appeared. But it's okay to say "intuitively, $G$ is acting like an expander". Do not say as part of a proof, "if the algorithm has made enough matches, then ..." unless you have precisely defined what that means. Better is to define a threshold $R(t)$ at each time $t$, then say "if the number of matches at time $t$ is at least $R(t)$, then...."
State results precisely using a logical sentence. Any proposition / lemma / theorem should really be a logical sentence such as "For all $x$ such that $P(x)$, there exists $y$ such that $Q(x,y)$. For example, "There exists a constant $c$ such that the following holds: For all input graphs on $n$ nodes, there exists $m$ such that Algorithm 4 runs in $m$ steps and $m \leq c n^3$."
First make sure you can write the result you are stating in this form, then see if you're willing to relax it to someting like "Algorithm 4 runs in time $O(n^3)$ on graphs of $n$ vertices". I would avoid something like "Algorithm 4 runs in cubic time" since it's unclear (cubic in what?).
Understand what a "step" of a proof is and use them well. A step in the proof starts with what has already been shown so far and applies a simple, known fact, axiom, or result (properly cited/stated) to get a new statement. For example, if we have already shown that $M \leq (1+x)^n$, then we can apply the fact that $1+x \leq e^x$ for all $x$ to deduce $M \leq e^{nx}$.
Even there I left out a step: $(e^x)^n = e^{nx}$. When in doubt, do not omit any step bigger than that. You can always cut them down later.
Your proof should be a sequence of steps of this kind, where the first step only uses assumptions stated in the claim, each step uses only statements shown in previous steps, and the last step derives the statement in the claim.
You should also split proofs into lemmas and so on, but that's beyond my scope.
In particular, each step should be short and easy to follow. If you are trying to write formally as a beginner, don't skip a bunch of lines of calculation and expect the reader to trust you. (If for some reason you do, at least tell the reader that's what you're doing!) The reader should be able to see immediately why this step is correct.
A big mistake beginning proof-writers make (also experienced ones) is to not bother writing why a seemingly-obvious step is true. This is a big red flag. Sit down and go through the math convincing yourself why that "obvious" step is true, then put that into the proof! Do not ever write "clearly" or "obviously". Give me the fact for why it's clear ("Because probabilities are at most $1$, $\sum p_i \leq n$").
When you proofread, do so extremely slowly, carefully, and pretend you're explaining to someone who has never seen your paper. Read it out loud if you have to. If you proofread in your head fast, you're just reminding yourself of what you intended it to say. A step or definition left out of the paper won't be noticed because it will still be in your head. You want to check that each sentence makes sense given (only) what came before it.
