#algortihm

I know many people are afraid of algorithms but I am pleased to say I have managed to game the system and train instagram algorithm to show me cute birbs every single time I open it

and I have managed to train google feeds algorithm to send me actual cracked games as official articles

My proof for this is showing there is an algorithm to 2-color any graph. Equivalently, you can use induction to do the algorithm backwards.

Algorithm:

Make a set (which starts empty) of "already colored points," and we'll call it C Choose a point and put it in C with the first color. While there are points not in C      Choose a point with an edge leading out of C      Color all vertices the point connects to with the color that the point is not      Put those points into C End the While loop

The first thing that could go wrong is if there is nothing to choose. Luckily, this cannot go wrong because a tree is connected, and so there is a path between any two points of the graph. We know that C is not empty, and the while loop still goes while there are things not in C. And, there is a path between those two points, and there must be a switch from C to not C.

C is connected, from how it is constructed. Because the tree is connected, C ends when the points in C are the points in the tree, so it ends with a coloring.

It can only give each point one color, because at any point, a point not in C has at most one edge to C. If it had two, that would make a cycle, invalidating that we are working in a tree. So, any step of the algorithm has C being a valid coloring.

Induction: A tree with one point clearly can be 2-colored.

If you assume any tree of size n-1 can be colored, then think of any tree of size n.

A tree always has a vertex of degree 1, so that vertex can be colored the other color than the one it is attached to.

So, a tree of size n is 2-colorable if a tree of size n-1 is 2-colorable, since one vertex is easy to color.

Here a talk by Roman Verostko