nyuuzyou/wikis huggingface dataset:
Kuratowski's Closure-Complement Problem/Closure

== Theorem ==
The closure of $A$ in $\R$ is given by:
:
== Proof ==
From Closure of Union of Adjacent Open Intervals:
:$\paren {\openint 0 1 \cup \openint 1 2}^- = \closedint 0 2$
From Real Number is Closed in Real Number Line:
:$\set 3$ is closed in $\R$
From Set is Closed iff Equals Topological Closure:
:$\set 3^- = \set 3$
From Closure of Rational Interval is Closed Real Interval:
:$\paren {\Q \cap \openint 4 5 }^- = \closedint 4 5$
The result follows from Closure of Finite Union equals Union of Closures.
Category:Kuratowski's Closure-Complement Problem
Category:Set Closures
Kuratowski's Closure-Complement Problem/Closure of Complement

== Theorem ==
The closure of the complement of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Complement:
From Real Number is Closed in Real Number Line:
:$\set 3$ is closed in $\R$
and:
:$\hointl \gets 0$ is closed in $\R$
and:
:$\hointr 5 \to$ is closed in $\R$
Then from Set is Closed iff Equals Topological Closure:
:$\set 3^- = \set 3$
:$\hointl \gets 0^- = \hointl \gets 0$
:$\hointr 5 \to^- = \hointr 5 \to$
From Closure of Half-Open Real Interval is Closed Real Interval:
:$\hointr 2 3 = \closedint 2 3$
and:
:$\hointl 3 4 = \closedint 3 4$
From Closure of Irrational Interval is Closed Real Interval:
:$\paren {\R \setminus \Q \cap \closedint 4 5}^- = \closedint 4 5$
From Closure of Finite Union equals Union of Closures:
The result follows.
Category:Kuratowski's Closure-Complement Problem
Kuratowski's Closure-Complement Problem/Closure of Interior

== Theorem ==
The closure of the interior of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Interior:
:$A^\circ = \openint 0 1 \cup \openint 1 2$
From Closure of Union of Adjacent Open Intervals:
:$A^{\circ \, -} = \closedint 0 2$
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Category:Set Closures
Kuratowski's Closure-Complement Problem/Closure of Interior of Closure

== Theorem ==
The closure of the interior of the closure of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Interior of Closure:
From Closure of Open Real Interval is Closed Real Interval:
:$\openint 0 2^- = \closedint 0 2$
and:
:$\openint 4 5^- = \closedint 4 5$
The result follows from Closure of Finite Union equals Union of Closures.
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Category:Set Closures
Kuratowski's Closure-Complement Problem/Closure of Interior of Complement

== Theorem ==
The closure of the interior of the complement of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Exterior:
From Closure of Open Real Interval is Closed Real Interval:
:$\openint \gets 0^- = \hointl \gets 0$
and:
:$\openint 5 \to^- = \hointr 5 \to$
From Closure of Union of Adjacent Open Intervals:
:$\paren {\openint 2 3 \cup \openint 3 4}^- = \closedint 2 4$
The result follows from Closure of Finite Union equals Union of Closures.
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Category:Set Closures
Category:Set Complement
Kuratowski's Closure-Complement Problem/Complement

== Theorem ==
The complement of $A$ in $\R$ is given by:
:
== Proof ==
For ease of analysis, let:
:$A_1 := \openint 0 1$
:$A_2 := \openint 1 2$
:$A_3 := \set 3$
:$A_4 := \Q \cap \openint 4 5$
Thus:
:$\ds A = \bigcup_{i \mathop = 1}^4 A_i$
By De Morgan's Laws:
:$\ds A' := \R \setminus A = \bigcap_{i \mathop = 1}^4 \paren {\R \setminus A_i}$
from which the result follows by inspection.
Category:Kuratowski's Closure-Complement Problem
Kuratowski's Closure-Complement Problem/Example

== Example for Kuratowski's Closure-Complement Problem ==
Let $\R$ be the real number line with the usual (Euclidean) topology.
Let $A \subseteq \R$ be defined as:
:
== Sources ==
* : Part $\text {II}$: Counterexamples: $32$. Special Subsets of the Real Line: $9$
Category:Kuratowski's Closure-Complement Problem
Kuratowski's Closure-Complement Problem/Exterior

== Theorem ==
The exterior of $A$ in $\R$ is given by:
:
== Proof ==
By definition, the exterior of $A$ in $\R$ can be defined either as:
:the complement of the closure of $A$ in $\R$: $A^{- \, \prime}$
or as:
:the interior of the complement of $A$ in $\R$: $A^{\prime \, \circ}$
From Kuratowski's Closure-Complement Problem: Closure:
It follows by inspection that:
Category:Kuratowski's Closure-Complement Problem
Category:Set Exteriors
Kuratowski's Closure-Complement Problem/Interior

== Theorem ==
The interior of $A$ in $\R$ is given by:
:
== Proof ==
From Interior equals Complement of Closure of Complement:
:$A^\circ = A^{\prime \, - \, \prime}$
From Kuratowski's Closure-Complement Problem: Closure of Complement:
It can be determined by inspection that:
:$A^{\prime \, - \, \prime} = \openint 0 1 \cup \openint 1 2$
Hence the result.
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Kuratowski's Closure-Complement Problem/Interior of Closure

== Theorem ==
The interior of the closure of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Closure:
From Interior of Closed Real Interval is Open Real Interval:
:$\closedint 0 2^\circ = \openint 0 2$
and:
:$\closedint 4 5^\circ = \openint 4 5$
From Interior of Singleton in Real Number Line is Empty:
:$\set 3^\circ = \O$
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Category:Set Closures
Kuratowski's Closure-Complement Problem/Interior of Closure of Interior

== Theorem ==
The interior of the closure of the interior of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Closure of Interior:
From Interior of Closed Real Interval is Open Real Interval:
:$\closedint 0 2^\circ = \openint 0 2$
Hence the result.
Category:Kuratowski's Closure-Complement Problem
Category:Examples of Set Interiors
Category:Set Closures
Kuratowski's Closure-Complement Problem/Interior of Complement of Interior

== Theorem ==
The interior of the complement of the interior of $A$ in $\R$ is given by:
:
== Proof ==
From Complement of Interior equals Closure of Complement:
:$A^{\circ \, \prime} = A^{\prime \, -}$
From Kuratowski's Closure-Complement Problem: Closure of Complement:
From Interior of Closed Real Interval is Open Real Interval:
:$\hointl \gets 0^\circ = \openint \gets 0$
and:
:$\hointr 2 \to^\circ = \openint 2 \to$
From Interior of Singleton in Real Number Line is Empty:
:$\set 1^\circ = \O$
Category:Kuratowski's Closure-Complement Problem
Category:Set Interiors
Category:Set Complement
Kuratowski's Closure-Complement Problem/Interior of Complement of Interior of Closure

== Theorem ==
The interior of the complement of the interior of the closure of $A$ in $\R$ is given by:
:
== Proof ==
From Kuratowski's Closure-Complement Problem: Interior of Closure:
By inspection:
From Interior of Closed Real Interval is Open Real Interval:
:$\left({\gets \,.\,.\, 0}\right]^\circ = \left({\gets \,.\,.\, 0}\right)$
and:
:$\left[{2 \,.\,.\, 4}\right]^\circ = \left({2 \,.\,.\, 4}\right)$
and:
:$\left[{5 \,.\,.\, \to}\right)^\circ = \left({5 \,.\,.\, \to}\right)$
Category:Kuratowski's Closure-Complement Problem
Kuratowski's Closure-Complement Problem/Mistake

== Source Work ==
:
:Part $\text {II}$: Counterexamples
::Section $32$: Special Subsets of the Real Line
:::Item $9$: Figure $12$
== Mistake ==
 and present a more complicated $14$-set than is necessary to demonstrate the theorem:
:$A := \set {\tfrac 1 n: n \in \Z_{>0} } \cup \openint 2 3 \cup \openint 3 4 \cup \set {4 \tfrac 1 2} \cup \closedint 5 6 \cup \paren {\hointr 7 8 \cap \Q}$
They present Figure $12$ to illustrate the various generated subsets graphically:
:
The following mistakes can be identified in the above diagram:
:$(1): \quad$ The set $A$ as presented expresses the interval of rationals as closed, whereas it is in fact half open.
:$(2): \quad$ The sets are all presented as subsets of $\R_{\ge 0}$, while this is not stated in the text.
:$(3): \quad$ $0$ is erroneously excluded from $A^{\prime}$.
A corrected version of this diagram is presented below:
: 
== Also see ==
* Kuratowski's Closure-Complement Problem
== Sources ==
* : Part $\text {II}$: Counterexamples: $32$. Special Subsets of the Real Line: $9$
Category:Mistakes/Counterexamples in Topology
Kuratowski's Closure-Complement Problem/Proof of Maximum

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $A \subseteq S$ be a subset of $T$.
By successive applications of the operations of complement relative to $S$ and the closure, there can be no more than $14$ distinct subsets of $S$ (including $A$ itself).
== Proof ==
Consider an arbitrary subset $A$ of a topological space $T = \struct {S, \tau}$.
To simplify the presentation:
:let $a$ be used to denote the operation of taking the complement of $A$ relative to $S$: $\map a A = S \setminus A$
:let $b$ be used to denote the operation of taking the closure of $A$ in $T$: $\map b A = A^-$
:let $I$ be used to denote the identity operation on $A$, that is: $\map I A = A$.
:let the parentheses and the reference to $A$ be removed, so as to present, for example:
::$\map a {\map b {\map a A} }$
:as:
::$a b a$
From Relative Complement of Relative Complement:
:$\map a {\map a A} = A$
or, using the compact notation defined above:
:$(1): \quad a a = I$
and from Closure of Topological Closure equals Closure:
:$\map b {\map b A} = \map b A = A^-$
or, using the compact notation defined above:
:$(2): \quad b b = b$
Let $s$ be a finite sequence of elements of $\set {a, b}$.
By successive applications of $(1)$ and $(2)$, it is possible to eliminate all multiple consecutive instances of $a$ and $b$ in $s$, and so reduce $s$ to one of the following forms:
:$\text{a)}: \quad a b a b \ldots a$
:$\text{b)}: \quad b a b a \ldots a$
:$\text{c)}: \quad a b a b \ldots b$
:$\text{d)}: \quad b a b a \ldots b$
From Closure of Complement of Closure is Regular Closed:
:$b a b$ is regular closed.
By Interior equals Complement of Closure of Complement, the interior of $A$ is:
:$a b a$
Recall the definition of regular closed:
:a set $A$ is regular closed it equals the closure of its interior.
And so as $b a b$ is regular closed:
:$b a b = b a b a \paren {b a b}$
So, adding an extra $b$ to either of $a b a b a b a$ or $b a b a b a$ will generate a string containing $b a b a b a b$ which can be reduced immediately to $b a b$.
It follows that the possible different subsets of $S$ that can be obtained from $A$ by applying $a$ and $b$ can be generated by none other than:
:$I$
:$a$
:$a b$
:$a b a$
:$a b a b$
:$a b a b a$
:$a b a b a b$
:$a b a b a b a$
:$b$
:$b a$
:$b a b$
:$b a b a$
:$b a b a b$
:$b a b a b a$
... a total of $14$.
Hence the result.
Category:Set Closures
Category:Relative Complement
Category:Kuratowski's Closure-Complement Problem
Kuratowski's Lemma

== Theorem ==
=== Formulation 1 ===
=== Formulation 2 ===
== Also known as ==
== Kuratowski's Lemma and Axiom of Choice ==
=== Axiom of Choice implies Kuratowski's Lemma ===
=== Kuratowski's Lemma implies Axiom of Choice ===
== Also see ==
== Historical Note ==
Category:Kuratowski's Lemma
Category:Maximal Principles
Category:Equivalents of Axiom of Choice
Kuratowski's Lemma/Formulation 1

== Theorem ==
Let $\struct {S, \preceq}, S \ne \O$ be a non-empty ordered set. 
Then every chain in $S$ is the subset of some maximal chain.
== Also known as ==
== Also see ==
== Historical Note ==
== Sources ==
* 
* 
* : Introduction to Set Theory: Notes
* 
Category:Kuratowski's Lemma
Kuratowski's Lemma/Formulation 2

== Theorem ==
Let $S$ be a set of sets which is closed under chain unions.
Then every element of $S$ is a subset of a maximal element of $S$ under the subset relation.
== Also known as ==
== Also see ==
== Historical Note ==
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 5$ Maximal principles
Category:Kuratowski's Lemma
Kuratowski's Lemma/Historical Note

== Historical Note on Kuratowski's Lemma ==
 published what is now known as Kuratowski's Lemma in $1922$, thinking it little more than a corollary of Hausdorff's Maximal Principle.
In $1935$, published his own equivalent, now known as Zorn's Lemma, acknowledging 's earlier work.
This later version became the more famous one.
== Sources ==
* 
* 
* : Introduction to Set Theory: Notes
Category:Historical Notes
Kuratowski's Lemma implies Tukey's Lemma

== Theorem ==
Let Kuratowski's Lemma be accepted as true.
Then Tukey's Lemma holds.
== Proof ==
Recall Kuratowski's Lemma:
Recall Tukey's Lemma:
So, let us assume Kuratowski's Lemma.
Let $S$ be a non-empty set of finite character.
From Class of Finite Character is Closed under Chain Unions, $S$ is closed under chain unions.
Then by Kuratowski's Lemma:
:every element of $S$ is a subset of a maximal element of $S$ under the subset relation.
Thus it is seen that Tukey's Lemma likewise holds.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 5$ Maximal principles: Proposition $5.5$
Category:Kuratowski's Lemma
Category:Tukey's Lemma
Kuratowski's Theorem

== Theorem ==
The following conditions on a graph $\Gamma$ are equivalent:
:$(1): \quad \Gamma$ is planar
:$(2): \quad \Gamma$ contains no subdivision of either the complete graph $K_5$ or the complete bipartite graph $K_{3, 3}$.
== Proof ==
Let $\Gamma$ be a graph with $V$ vertices, $E$ edges and $F$ faces.
The proof proceeds in two parts: $(1) \implies (2)$ and $(2) \implies (1)$.
=== $(1)$ implies $(2)$ ===
First we consider $K_5$. 
$K_5$ has $5$ vertices and $10$ edges.
By the Euler Polyhedron Formula, a planar embedding would have $7$ faces. 
But each face has at least $3$ edges, while each edge bounds at most two faces.
Suppose we count the incident edge-face pairs.
Then the number of faces is at most:
:$E \dfrac 2 3 = 6 \dfrac 2 3$
which contradicts the deduction that $K_5$, if planar, should have $7$ faces.
Hence $K_5$ is non-planar.
Now consider $K_{3, 3}$.
$K_{3, 3}$ has $6$ vertices and $9$ edges.
Hence $K_{3, 3}$ has $5$ faces if it is planar.
Since $K_{3, 3}$ is bipartite, from Graph is Bipartite iff No Odd Cycles, each cycle in $K_{3,3}$ has an even number of edges.
Hence any face must have at least $4$ edges.
So the number of faces is at most
:$E \dfrac 2 4 = 4 \dfrac 1 2$
which contradicts the deduction that $K_{3, 3}$, if planar, should have $5$ faces.
Hence $K_{3, 3}$ is non-planar.
Now consider a subdivision of either graph.
The arguments as above continue to work as before, since both $V$ and $E$ have increased by one in the Euler formula.
So the expected value of $F$ is unchanged.
Hence if a graph $\Gamma$ contains a subdivision of $K_5$ or $K_{3,3}$, then $\Gamma$ is not planar.
Taking the contrapositive:
:$\Gamma$ is a planar graph $\implies \Gamma$ does not contain a subdivision of either $K_5$ or $K_{3, 3}$.
=== $(2)$ implies $(1)$ ===
== Sources ==
* 
* 
Category:Graph Theory
Kurtosis in terms of Non-Central Moments

== Theorem ==
Let $X$ be a random variable with expectation $\mu$ and standard deviation $\sigma$.
Then the kurtosis $\alpha_4$ of $X$ is given by: 
:$\ds \alpha_4 = \dfrac {\expect {X^4} - 4 \mu \expect {X^3} + 6 \mu^2 \expect {X^2} - 3 \mu^4} {\sigma^4}$
== Proof ==
Category:Kurtosis
Kurtosis of Normal Distribution

== Theorem ==
Let $X$ be a continuous random variable with a normal distribution with parameters $\mu$ and $\sigma^2$ for some $\mu \in \R$ and $\sigma \in \R_{> 0}$:
:$X \sim \Gaussian \mu {\sigma^2}$
Then the kurtosis $\alpha_4$ of $X$ is equal to $3$.
That is, $\Gaussian \mu {\sigma^2}$ is mesokurtic.
== Proof ==
From the definition of kurtosis, we have: 
:$\alpha_4 = \expect {\paren {\dfrac {X - \mu} \sigma}^4}$
where: 
:$\mu$ is the expectation of $X$. 
:$\sigma$ is the standard deviation of $X$.
By Expectation of Normal Distribution, we have: 
:$\mu = \mu$
By Variance of Normal Distribution, we have: 
:$\sigma = \sigma$ 
So: 
To calculate $\alpha_4$, we must calculate $\expect {X^4}$.
We find this using the moment generating function of $X$, $M_X$. 
From Moment in terms of Moment Generating Function:
:$\expect {X^4} = \map { {M_X}^{\paren 4} } 0$
From Moment Generating Function of Normal Distribution: Fourth Moment: 
:$\map { {M_X}^{\paren 4} } t = \paren {3 \sigma^4 + 6 \sigma^2 \paren {\mu + \sigma^2 t}^2 + \paren {\mu + \sigma^2 t}^4} \map \exp {\mu t + \dfrac 1 2 \sigma^2 t^2}$
Setting $t = 0$ and from Exponential of Zero, we have:
Plugging this result back into our equation above:
== Also see ==
* Definition:Mesokurtic: a random variable with a kurtosis equal to $3$
== Sources ==
* 
* 
* 
* 
* 
Category:Kurtosis
Category:Normal Distribution
Kusmin-Landau Inequality

== Theorem ==
Let $I$ be the half-open interval $\hointl a b$.
Let $f: I \to R$ be continuously differentiable.
Let $f'$ be monotonic.
Let $\norm {f'} \ge \lambda$ on $I$ for some $\lambda \in \R_{>0}$, where $\norm {\, \cdot \,}$ denotes the distance to nearest integer.
Then:
:$\ds \sum_{n \mathop \in I} e^{2 \pi i \map f n} = \map \OO {\frac 1 \lambda}$
where the big-$\OO$ estimate does not depend on $f$.
== Proof ==
== Sources ==
* : Theorem $2.1$
Category:Exponential Sums
König's Lemma

== Lemma ==
Let $G$ be an infinite graph which is connected and is locally finite.
Then every vertex lies on a path of infinite length.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Note ==
If the graph $G$ is assumed to be countably infinite, then the result will hold in pure Zermelo-Fraenkel set theory without any choice.
== Linguistic Note ==
Category:Graph Theory
Category:König's Lemma
König's Lemma/Countable

== Theorem ==
Let $G = \struct {V, E}$ be a graph with countably infinitely many vertices which is connected and is locally finite.
Then every vertex of $G$ lies on a path of infinite length.
== Proof ==
Let $r$ be a vertex of $G$.
Recursively define a sequence $\sequence {S_n}$:
Let $S_0 = \set r$.
Let $S_{n + 1}$ be the set of all vertices that are adjacent to some element of $S_n$ but not adjacent to any element of $S_k$ for $k < n$.
That is, $S_n$ is the set of vertices whose shortest path(s) to $r$ have $n$ edges.
Since $G$ is connected:
:$\ds V = \bigcup_{n \mathop \in \N} S_n$
Note that $\set {S_n: n \in \N}$ is pairwise disjoint.
Define a relation $\RR$ on $V$ by letting $p \mathrel \RR q$ :
:$p$ is adjacent to $q$
and:
:there exists an $n \in \N$ such that $p \in S_n$ and $q \in S_{n + 1}$.
Let $\RR^+$ be the transitive closure of $\RR$.
Let $V'$ be the set of all $v \in V$ such that $\map {\RR^+} v$ is infinite.
It will be demonstrated that $r \in V'$:
Let $v \in V$.
Since $G$ is connected, there is a path from $r$ to $v$.
By the Well-Ordering Principle, there is a path $P$ from $r$ to $v$ of minimal length.
Then the vertices along $P$ will lie in successive sets $S_k$.
Thus $v \in \map {\RR^+} r$.
As this holds for all $v \in V$, and $V$ is infinite, $\map {\RR^+} r$ is infinite.
Therefore $r \in V'$.
Let $\RR'$ be the restriction of $\RR$ to $V'$.
It is to be shown that $\RR'$ is a left-total relation.
Let $v \in V'$.
Then $\map {\RR^+} v$ is infinite.
Since $\map \RR v$ is finite, Finite Union of Finite Sets is Finite shows that $\map \RR v$ must have an element $u$ such that $\map {\RR^+} u$ is infinite.
So $u \in V'$ and $v \mathrel {\RR'} u$.
We have that $V$ is assumed to be countably infinite.
, let $V = \N$.
Recursively define a sequence $\sequence {v_k}$ in $V'$ thus:
:$v_0 = r$
:$v_{n + 1} = \map \min {\map {\RR'} {v_n} }$
Then $\sequence {v_k}$ is the sequence of vertices along an infinite path starting at $r$.
Category:König's Lemma
König's Lemma/Proof 1

== Lemma ==
== Proof ==
Let $G$ be an infinite graph which is connected and is locally finite.
From Vertices in Locally Finite Graph, $G$ has an infinite number of vertices $v_1, v_2, \ldots, v_k, \ldots$, each of finite degree.
Let $\VV_k$ be the set of all vertices adjacent to $v_k$.
As $G$ is a connected graph, between $v_k$ and every other vertex of $G$ there exists at least one open path from $v_k$ to every other vertex of $G$.
Take any vertex of $G$ and call it $v_1$.
Let $\PP_1$ be the set of all paths from $v_1$.
Each element of $\PP_1$ must start with an edge joining $v_1$ to some element of $\VV_1$.
There must be some $v_r \in \VV_1$ such that there is an infinite path from $v_r$ in $G$ which does not pass through $v_1$. Otherwise, every path from $v_1$ would be finite, and since there is a path from $v_1$ to each other vertex of the graph, all vertices are contained within one of these finite paths. There are a finite number of paths from $v_1$, so all vertices of $G$ are contained within a finite set of finite sets, contradicting the assumption that $G$ is infinite.
By the axiom of dependent choice, we may pick one of the vertices of $V_1$ such that there exists an infinite path through it that does not include $v_1$, and call this $v_2$.
Each such infinite path must start with one of the elements of $\VV_2$.
Repeating the above argument shows that there is some $v_s \in \VV_2$ such that there is an infinite path from $v_s$ in $G$ which does not pass through $v_2$.
Thus we can construct by induction an infinite path.
The induction hypothesis states that there are infinitely many vertices which can be reached by a path from a particular vertex $v_i$ that does not go through one of a finite set of vertices.
The induction argument is that one of the vertices adjacent to $v_i$ satisfies the induction hypothesis, even when $v_i$ is added to the finite set.
The result of this induction argument is that for all $n$ we can choose a vertex $v_n$ as per the construction.
The set of vertices chosen in the construction is then a path, because each one was chosen to be adjacent to the previous one, and the construction guarantees that the same vertex is never chosen twice.
Category:König's Lemma
König's Lemma/Proof 2

== Lemma ==
== Proof ==
Let $G$ be an infinite graph which is both connected and locally finite.
From Vertices in Locally Finite Graph, $G$ has an infinite number of vertices each of finite degree.
Let $v$ be a vertex of $G$.
Let $T$ be the set of all finite open paths that start at $v$.
Define the ordering $\preccurlyeq$ on $T$ as follows:
Let $\tuple {v_0, e_0, v_1, e_1, \ldots, v_m} \preccurlyeq \tuple {v'_0, e'_0, v'_1, e'_1, \ldots, v'_n}$ :
:$m \le n$
and:
:$\forall i < m: \tuple {v'_i, e'_i, v'_{i + 1} } = \tuple {v_i, e_i, v_{i + 1} }$
Observe that $T$ is a tree.
For each vertex $x$, let $\map E x$ be the set of all edges incident on $x$.
$\map E x$ is finite because $G$ is locally finite by definition.
For every $\tuple {v_0, e_0, v_1, e_1, \ldots, v_{n + 1} } \in T$ we have that $e_n \in \map E {v_n}$.
It follows that $T$ is finitely branching. 
By definition of connectedness, to every vertex $x$ there is a walk $w$ from $v$.
Suppose $w = \tuple {v_0, e_0, v_1, e_1, \ldots, v_n}$ contains a cycle $\tuple {v_i, e_i, v_{i + 1}, \ldots, v_j}$ where $v_i = v_j$.
Then we can delete $\tuple {e_i, v_{i + 1}, \ldots, v_j}$ from $w$ to get a shorter walk from $v$ to $x$.
Repeatedly deleting cycles until none remain, we obtain an open path from $v$ to $x$.
There exist an infinite number of points in $G$, as, by definition of locally finite, $G$ is itself infinite.
We have just demonstrated that for each $x \in G$ there exists an open path from $v$ to $x$.
Hence $T$, the set of finite paths that start at $v$, is infinite.
By Kőnig's tree lemma, $T$ has an infinite branch $B$.
The union $\bigcup B$ is then an infinite path in $G$ that contains $v$.
Category:König's Lemma
König's Theorem

* König's Theorem (Set Theory): an equivalent formulation to the Axiom of Choice.
* König's Theorem (Graph Theory): on the number of edges in a bipartite graph.
* König's Theorem (Kinetics): the kinetic energy of a system of particles is the kinetic energy associated to the movement of the center of mass and the kinetic energy associated of the movement of the particles relative to the center of mass.
There is also:
* König's Lemma: a sufficient condition for an infinite graph to have an infinitely long path.
* A special case of this: König's Tree Lemma.