Let $\mathrm{odd}(H)$ denote the number of odd components of the graph $H$.
Let $G$ be a connected cubic graph with no more than two cut-edges.
Assume by way of contradiction that $G$ has no perfect matching.
Since the number of vertices of $G$ is even, if $G$ has no perfect matching then a maximum size matching in $G$ must miss at least two vertices and so, by theorem Tutte-Berge theorem, there is a subset $S$ of $V(G)$ such that $|S|\le\mathrm{odd}(G\setminus S)-2$. Each odd component of $G\setminus S$ has an odd number of vertices of odd degree and therefore each odd component of $G\setminus S$ is joined to $S$ by an odd number of edges. If this odd number is one, the corresponding edge must be a cut-edge. By our hypothesis it follows all but at most two components of $G\setminus S$ are joined to $S$ by at least three edges,
hence the odd components are joined to $S$ by at least
$$
3(\mathrm{odd}(G\setminus S)-2)+2\ge3|S|+2
$$
edges. But the number of edges in $G$ ending on vertices in $S$ is at most
$3|S|$, and we have arrived at a contradiction.
Remark: The Tutte-Berge theorem asserts that the number of vertices not covered by a matching of maximum size is $\max_{S\subseteq V(G)}\{\mathrm{odd}(G\setminus S)-|S|\}$
There are many ways to construct triangle-free graphs with large chromatic number. One well-known construction is Jan Mycielski's, which is described in the Wikipedia article that you cited; I guess you had trouble understanding it. Instead of explaining Mycielski's construction, I will describe another one, which is even less "efficient" (meaning that it produces a bigger graph for a given chromatic number) but maybe slightly simpler.
For a given natural number $n\in\mathbb N$, let $G_n$ be the following graph with $\binom n2$ vertices and $\binom n3$ edges: the vertices are the pairs $(x,y)$ of integers with $1\le x\lt y\le n$; for each triple $(x,y,z)$ with $1\le x\lt y\lt z\le n$, there is an edge joining vertex $(x,y)$ to vertex $(y,z)$. It is plain to see that $G_n$ is triangle-free. I will show that $G_n$ is $k$-colorable if and only if $n\le2^k$. Therefore, if $2^{1525}\lt n\le2^{1526}$, then $\chi(G_n)=1526$.
First, suppose $G_n$ is $k$-colorable; I will show that $n\le2^k$. Let $f:V(G_n)\to[k]=\{1,\dots,k\}$ be a proper vertex-coloring of $G_n$; i.e., for $1\le x\lt y\le n$, the vertex $(x,y)$ gets color $f(x,y)\in[k]$. For each $x\in[n]=\{1,\dots,n\}$, let $S_x=\{f(u,x):1\le u\lt x\}\subseteq[k]$. Note that, since $f$ is a proper coloring, the sets $S_1,\dots,S_n$ must be distinct; namely, if $1\le x\lt y\le n$, then $f(x,y)\in S_y\setminus S_x$, showing that $S_x\ne S_y$. Thus there are $n$ distinct subsets of $[k]$, i.e., $n\le2^k$.
Now, suppose $n\le2^k$; I will show that $G_n$ is $k$-colorable. Let $S_1,\dots,S_n$ be $n$ distinct subsets of $[k]$, indexed in order of increasing size, so that $|S_1|\le|S_2|\le\dots\le|S_n|$; it follows that $S_y\not\subseteq S_x$ whenever $1\le x\lt y\le n$. Finally, we get a proper coloring $f:V(G)\to[k]$ by assigning to each vertex $(x,y)$ a color $f(x,y)\in S_y\setminus S_x$.
Best Answer
The idea is that an ordered pair representing an amount of water one can obtain in each bucket represents a node in a graph. The directed edges of the graph represent which states are obtainable in one move from the current state.
Solving for the least number of steps to obtain precisely $k$ liters is then a shortest path problem. You are searching the graph for the shortest path from the original state to a state that has $k$ as one the members of the ordered pair.