nyuuzyou/wikis huggingface dataset:
Goldbach's Lesser Conjecture/Historical Note

== Historical Note on Goldbach's Lesser Conjecture ==
 conjectured in a letter to dated $18$ November $1752$ that all odd integers are expressible in the form $2 a^2 + p$, for $a \ge 0$ and $p$ prime.
At that time, $1$ was considered to be prime. Thus $1 = 2 \times 0^2 + 1$ and $3 = 2 \times 1^2 + 1$ were considered to fit the criteria, as was $17 = 0^2 + 17$.
The conjecture was believed to hold until $1856$, when and his students tested all the primes to $9000$, and found the counterexamples $5777$ and $5993$.
== Sources ==
* 
* 
Category:Historical Notes
Goldbach's Theorem

== Theorem ==
Let $F_m$ and $F_n$ be Fermat numbers such that $m \ne n$.
Then $F_m$ and $F_n$ are coprime.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 2.4$: The rational numbers and some finite fields: Further Exercises $9$
* : $257$
* 
* 
* : Theorem $4.1$
Category:Fermat Numbers
Category:Coprime Integers
Category:Goldbach's Theorem
Goldbach's Theorem/Proof 1

== Theorem ==
== Proof ==
 $F_m$ and $F_n$ have a common divisor $p$ which is prime.
As both $F_n$ and $F_m$ are odd, it follows that $p$ must itself be odd.
, suppose that $m > n$.
Then $m = n + k$ for some $k \in \Z_{>0}$.
Hence $p = 2$.
However, it has already been established that $p$ is odd.
From this contradiction it is deduced that there is no such $p$.
Hence the result.
Category:Goldbach's Theorem
Goldbach's Theorem/Proof 2

== Theorem ==
== Proof ==
Let $F_m$ and $F_n$ be Fermat numbers such that $m < n$.
Let $d = \gcd \set {F_m, F_n}$.
From the corollary to Product of Sequence of Fermat Numbers plus 2:
:$F_m \divides F_n - 2$
But then:
But all Fermat numbers are odd, so:
:$d \ne 2$
It follows that $d = 1$.
The result follows by definition of coprime.
Category:Goldbach's Theorem
Goldbach's Weak Conjecture

== Theorem ==
Every odd integer greater than $7$ is the sum of three odd primes.
== Proof ==
== Also known as ==
It is also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem
== Historical Note ==
== Also see ==
* Goldbach Conjecture
* Goldbach's Marginal Conjecture
* Goldbach Conjecture implies Weak Goldbach Conjecture, which is why this one is called weak.
Category:Goldbach Conjecture
Goldbach's Weak Conjecture/Historical Note

== Historical Note on Goldbach's Weak Conjecture ==
* 1923: It was proved by and that the Generalized Riemann Hypothesis implies Goldbach's Weak Conjecture for sufficiently large numbers.
* 1937: It was proved by , independently of the Generalized Riemann Hypothesis, that all sufficiently large numbers can be expressed as the sum of three primes.
* 1939: 's student proved that $3^{14348907}$ is large enough.
* 1997: Proved by , , and that the Generalized Riemann Hypothesis implies Goldbach's Weak Conjecture.
* 2002: and lowered the threshold for 's result to approximately $n > e^{3100}$, which is roughly $2 \times 10^{1346}$. This gives an upper bound such that it is feasible to test any single odd number below that threshold. Though one can calculate: if a modern desktop were the size of a 1cm cube, one filled the solar system with such cubes and left them running the fastest known algorithms since the beginning of time, numbers larger than $10^{70}$ would remain untested. For this reason the problem is still considered unsolved, though the existence of only finitely many counterexamples is a worthwhile result in its own right.
* 2013: proves the conjecture.
Category:Historical Notes
Goldbach Conjecture

== Conjecture ==
Every even integer greater than $2$ is the sum of two primes.
=== Marginal Conjecture ===
== Landau's Problems ==
This is the $1$st of Landau's problems.
== Also see ==
* Goldbach's Weak Conjecture
* Goldbach Conjecture implies Goldbach's Marginal Conjecture
== Historical Note ==
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
* : $2$
* : $2$
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Goldbach Conjecture
Category:Landau's Problems
Category:Prime Numbers
Category:Unproven Hypotheses
Goldbach Conjecture/Historical Note

== Conjecture ==
 actually proposed what is now known as Goldbach's Marginal Conjecture in $1742$ in a letter to . then proposed this stronger conjecture.
It was published in 's of $1770$.
It has been checked by computer for numbers up to at least $10^{18}$.
In $1937$ proved Vinogradov's Theorem: that all sufficiently large odd numbers are the sum of $3$ primes.
In $1973$ proved Chen's Theorem: that every sufficiently large even number is the sum of a prime and either another prime or a semiprime.
In $1995$ showed in Ramaré's Theorem that every even number is the sum of no more than $6$ primes.
== Sources ==
* 
* 
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Historical Notes
Goldbach Conjecture/Marginal

== Goldbach's Marginal Conjecture ==
Every integer greater than $5$ can be written as the sum of three primes.
== Also see ==
* Goldbach Conjecture implies Goldbach's Marginal Conjecture
== Historical Note ==
== Sources ==
* : Chapter $7$: Patterns in Numbers: Fermat
Category:Unproven Hypotheses
Category:Hilbert 23
Category:Prime Numbers
Category:Goldbach Conjecture
Goldbach Conjecture implies Goldbach's Marginal Conjecture

== Theorem ==
Suppose the Goldbach Conjecture holds:
:Every even integer greater than $2$ is the sum of two primes.
Then Goldbach's Marginal Conjecture follows:
:Every integer greater than $5$ can be written as the sum of three primes.
== Proof ==
Suppose the Goldbach Conjecture holds.
Let $n \in \Z$ such that $n > 5$.
Let $n$ be an odd integer.
Then $n - 3$ is an even integer greater than $2$.
By the Goldbach Conjecture:
:$n - 3 = p_1 + p_2$
where $p_1$ and $p_2$ are both primes.
Then:
:$n = p_1 + p_2 + 3$
As $3$ is prime, the result follows.
Let $n$ be an even integer.
Then $n - 2$ is an even integer greater than $3$ and so greater than $2$.
By the Goldbach Conjecture:
:$n - 2 = p_1 + p_2$
where $p_1$ and $p_2$ are both primes.
Then:
:$n = p_1 + p_2 + 2$
As $2$ is prime, the result follows.
Category:Prime Numbers
Category:Goldbach Conjecture
Goldbach Conjecture implies Weak Goldbach Conjecture

== Theorem ==
The Goldbach Conjecture:
: Every even integer greater than $2$ is the sum of two primes
implies Goldbach's Weak Conjecture:
: Every odd integer greater than $7$ is the sum of three odd primes.
== Proof ==
Take any odd integer $n$ such that $n > 7$.
Then $m = n - 3$ is an even integer $n$ such that $m > 4$.
If the Goldbach Conjecture holds, then $m$ is the sum of two primes: $m = p_1 + p_2$.
If one of them were $2$, then $m - 2$ would have to be even, which if it is prime it can not be.
So if $m > 4$, both $p_1$ and $p_2$ must be odd.
So then we have that $n = p_1 + p_2 + 3$, that is, the sum of three odd primes.
So, if the Goldbach Conjecture holds, then so does Goldbach's Weak Conjecture.
Category:Number Theory
Category:Goldbach Conjecture
Goldbach implies Bertrand

== Theorem ==
Bertrand's Postulate is a logical consequence of the truth of the Goldbach Conjecture:
: Bertrand's Postulate: $\forall n \in \N: n > 1:$ between $n$ and $2n$ lies a prime number $p$:
::$n < p < 2n$
: (Strong) Goldbach Conjecture: Every even number greater than $2$ can be written as a sum of two prime numbers.
== Proof ==
Assume the truth of the Goldbach Conjecture.
Since $n > 1$, we have that $2 n$ is an even integer greater than $2$.
From the Goldbach Conjecture, $2n = p_1 + p_2$ for some prime numbers $p_1$ and $p_2$.
We have that $p_1, p_2 < n \implies p_1 + p_2 < 2n$.
Therefore, at least one of $p_1, p_2 \ge n$.
That is, $n \le p_i < 2n$.
If $n$ is not a prime, the strict inequality holds.
On the other hand, suppose $n$ is prime.
:$(1): \quad$ Consider the case $n = 2$.
For $2 < 3 < 2 \times 2$ (and $3 \in \Bbb P$) Bertrand's Postulate holds with $p=3$. 
:$(2): \quad$ Otherwise $n > 2$, and so $n$ is an odd prime.
Then $n + 1$ is composite, because of being even.
So $2 \left({n + 1}\right) = p'_1 + p'_2$, where $p'_1$ or $p'_2$ must be greater than $n + 1$.
That is, either $p'_1 > n$ or $p'_2 > n$.
, suppose $p'_2 > n$.
Then, $n < p'_2 < 2n + 2$.
But $p'_2 \ne 2n + 1$, or else $p'_1 = 1$.
Also $p'_2 \ne 2n$ since $2n$ is composite.
So $n < p'_2 < 2n$.
So, if the Goldbach Conjecture were to be true, it would logically imply the truth of Bertrand's Postulate.
== Sources ==
* 
Category:Number Theory
Golden Mean as Root of Quadratic

== Theorem ==
The golden mean $\phi$ is one of the roots of the quadratic equation:
:$x^2 - x - 1 = 0$
The other root is $\hat \phi = 1 - \phi$.
== Proof ==
By Solution to Quadratic Equation:
Thus
:$x = \dfrac {1 + \sqrt 5} 2$
and:
:$x = \dfrac {1 - \sqrt 5} 2$
The result follows:
By definition of golden mean:
:$\phi = \dfrac {1 + \sqrt 5} 2$
From Closed Form of One Minus Golden Mean:
:$\hat \phi = 1 - \phi = \dfrac {1 - \sqrt 5} 2$
Category:Golden Mean
Golden Mean is Irrational

== Theorem ==
The golden mean $\phi$ is irrational.
== Proof ==
By definition of golden mean:
:$\phi = \dfrac {1 + \sqrt 5} 2$
By Square Root of Prime is Irrational:
:$\sqrt 5$ is irrational.
By Rational Number plus Irrational Number is Irrational:
:$1 + \sqrt 5$ is irrational.
By Irrational Number divided by Rational Number is Irrational:
:$\dfrac {1 + \sqrt 5} 2$ is irrational.
== Sources ==
* : $\S 1.2.2$: Numbers, Powers, and Logarithms
Category:Golden Mean
Gradient Operator Distributes over Addition

== Theorem ==
Let $\mathbf V$ be a vector space of $n$ dimensions.
Let $\tuple {\mathbf e_1, \mathbf e_2, \ldots, \mathbf e_n}$ be the standard ordered basis of $\mathbf V$.
Let $\map f {x_1, x_2, \ldots, x_n}, \map g {x_1, x_2, \ldots, x_n}: \mathbf V \to \R$ be differentiable real-valued functions on $\mathbf V$.
Let $\nabla f$ denote the gradient of $f$.
Then:
:$\nabla \paren {f + g} = \nabla f + \nabla g$
== Proof ==
== Sources ==
* : $\S 22$: Miscellaneous Formulas involving $\nabla$: $22.35$
Category:Gradient Operator
Gradient Operator is Invariant under Coordinate Transformation

== Theorem ==
Let $R$ be a region of space in which there exists an scalar field $F$.
Let $\mathbf V$ denote the gradient of $F$.
Then $\mathbf V$ is invariant under a change of coordinate system on $R$.
== Proof ==
The result follows directly from the geometrical representation of the gradient operator.
== Sources ==
* : Chapter $\text {IV}$: The Operator $\nabla$ and its Uses: $2$. The Gradient of a Scalar Field
Category:Gradient Operator
Gradient of Divergence

== Theorem ==
Let $\map {\R^3} {x, y, z}$ denote the real Cartesian space of $3$ dimensions.
Let $\tuple {\mathbf i, \mathbf j, \mathbf k}$ be the standard ordered basis on $\R^3$.
Let $\mathbf V: \R^3 \to \R^3$ be a vector field on $\R^3$:
:$\mathbf V := \tuple {\map {V_x} {x, y, z}, \map {V_y} {x, y, z}, \map {V_z} {x, y, z} }$
Then:
:$\map \grad {\operatorname {div} \mathbf V} = \paren {\dfrac {\partial^2 V_x} {\partial x^2} + \dfrac {\partial^2 V_y} {\partial x \partial y} + \dfrac {\partial^2 V_z} {\partial x \partial z} } \mathbf i + \paren {\dfrac {\partial^2 V_x} {\partial x \partial y} + \dfrac {\partial^2 V_y} {\partial y^2} + \dfrac {\partial^2 V_z} {\partial y \partial z} } \mathbf j + \paren {\dfrac {\partial^2 V_x} {\partial x \partial z} + \dfrac {\partial^2 V_y} {\partial y \partial z} + \dfrac {\partial^2 V_z} {\partial z^2} } \mathbf k$
where:
:$\grad$ denotes the gradient operator
:$\operatorname {div}$ denotes the divergence operator.
== Proof ==
From Divergence Operator on Vector Space is Dot Product of Del Operator and definition of the gradient operator:
where $\nabla$ denotes the del operator.
Hence:
== Examples ==
== Sources ==
* : Chapter $\text {V}$: Further Applications of the Operator $\nabla$: $4$. The Operator $\grad \operatorname {div}$: $(5.5)$
Category:Gradient Operator
Category:Divergence Operator
Category:Gradient of Divergence
Gradient of Divergence/Examples/Fluid Density Increase

== Example of Use of Gradient of Divergence ==
Let $\mathbf V$ be the velocity of a fluid at a point in a region of space $R$.
We have that $\operatorname {div} \mathbf V$ is the scalar rate of change of density with respect to time.
Hence $\grad \operatorname {div} \mathbf V$ gives the magnitude and direction in space of the greatest rate of increase of the space of the density.
== Sources ==
* : Chapter $\text {V}$: Further Applications of the Operator $\nabla$: $4$. The Operator $\grad \operatorname {div}$
Category:Gradient of Divergence
Category:Fluid Mechanics
Gradient of Divergence/Examples/Increase of Electric Charge

== Example of Use of Gradient of Divergence ==
Let $\mathbf V$ be an electric force in a given electric field at a point in a region of space $R$.
We have that $\operatorname {div} \mathbf V$ is the space charge density.
Hence $\grad \operatorname {div} \mathbf V$ gives the magnitude and direction in space of the greatest rate of increase of the space of the electric charge at a given point.
== Sources ==
* : Chapter $\text {V}$: Further Applications of the Operator $\nabla$: $4$. The Operator $\grad \operatorname {div}$
Category:Gradient of Divergence
Category:Fluid Mechanics
Gradient of Divergence is Conservative

== Theorem ==
Let $\map {\R^3} {x, y, z}$ denote the real Cartesian space of $3$ dimensions.
Let $\mathbf V$ be a vector field on $\R^3$:
Then the gradient of the divergence of $\mathbf V$ is a conservative vector field.
== Proof ==
The divergence of $\mathbf V$ is by definition a scalar field.
Then from Vector Field is Expressible as Gradient of Scalar Field iff Conservative it follows that $\grad \operatorname {div} \mathbf V$ is a conservative vector field.
== Sources ==
* : Chapter $\text {V}$: Further Applications of the Operator $\nabla$: $4$. The Operator $\grad \operatorname {div}$
Category:Gradient Operator
Category:Divergence Operator
Category:Conservative Vector Fields
Gradient of Dot Product

== Definition ==
Let $\map {\R^3} {x, y, z}$ denote the real Cartesian space of $3$ dimensions..
Let $\tuple {\mathbf i, \mathbf j, \mathbf k}$ be the standard ordered basis on $\R^3$.
Let $\mathbf f$ and $\mathbf g: \R^3 \to \R^3$ be vector-valued functions on $\R^3$:
:$\mathbf f := \tuple {\map {f_x} {\mathbf x}, \map {f_y} {\mathbf x}, \map {f_z} {\mathbf x} }$
:$\mathbf g := \tuple {\map {g_x} {\mathbf x}, \map {g_y} {\mathbf x}, \map {g_z} {\mathbf x} }$
Let $\nabla \mathbf f$ denote the gradient of $f$.
Then:
:$\map \nabla {\mathbf f \cdot \mathbf g} = \paren {\mathbf g \cdot \nabla} \mathbf f + \paren {\mathbf f \cdot \nabla} \mathbf g + \mathbf g \times \paren {\nabla \times \mathbf f} + \mathbf f \times \paren {\nabla \times \mathbf g}$
where:
:$\mathbf f \times \mathbf g$ denotes vector cross product
:$\mathbf f \cdot \mathbf g$ denotes dot product
== Proof ==
Then:
and similarly:
Next:
and:
Combining in pairs:
and:
Finally combining all four terms:
== Sources ==
* : $\S 22$: Miscellaneous Formulas involving $\nabla$: $22.42$
Category:Gradient Operator
Category:Dot Product
Gradient of Newtonian Potential

== Theorem ==
Let $R$ be a region of space.
Let $S$ be a Newtonian potential over $R$ defined as:
:$\forall \mathbf r = x \mathbf i + y \mathbf j + z \mathbf k \in R: \map S {\mathbf r} = \dfrac k r$
where:
:$\tuple {\mathbf i, \mathbf j, \mathbf k}$ is the standard ordered basis on $R$
:$\mathbf r = x \mathbf i + y \mathbf j + z \mathbf k$ is the position vector of an arbitrary point in $R$ with respect to the origin
:$r = \norm {\mathbf r}$ is the magnitude of $\mathbf r$
:$k$ is some predetermined constant.
Then:
:$\grad S = -\dfrac {k \mathbf r} {r^3} = -\dfrac {k \mathbf {\hat r} } {r^2}$
where:
:$\grad$ denotes the gradient operator
:$\mathbf {\hat r}$ denotes the unit vector in the direction of $\mathbf r$.
The fact that the gradient of $S$ is negative indicates that direction of the vector quantities that compose the vector field that is $\grad S$ all point towards the origin.
== Proof ==
From the geometry of the sphere, the equal surfaces of $S$ are concentric spheres whose centers are at the origin.
As the origin is approached, the scalar potential is unbounded above.
We have:
== Sources ==
* : Chapter $\text {V}$: Further Applications of the Operator $\nabla$: $9$. The Vector Field $\map \grad {k / r}$: $(5.11)$
Category:Gradient Operator
Category:Newtonian Potentials
Graeco-Latin Square/Examples/Order 3

== Example of Graeco-Latin Square ==
The following is an example of a Graeco-Latin square of order $3$:
$\begin{array} {|c|c|c|}
\hline A \alpha & B \beta & C \gamma \\
\hline B \gamma & C \alpha & A \beta \\
\hline C \beta & A \gamma & B \alpha \\
\hline \end{array}$
== Sources ==
* 
* 
Category:Examples of Graeco-Latin Squares
Gram-Equivalent/Examples/Oxygen in Water

== Example of Gram-Equivalent ==
$1$ gram of hydrogen combines with $8$ grams of oxygen to make $9$ grams of water.
Thus the gram-equivalent of oxygen in water is $8$ grams
== Sources ==
* : $1$: Simple models of the atom: $\text {1-3}$: The Electrical Structure of Matter
Category:Examples of Gram-Equivalents
Gram-Schmidt Orthogonalization/Also known as

== Gram-Schmidt Orthogonalization: Also known as == 
Gram-Schmidt Orthogonalization is known in some texts as Gram-Schmidt Orthonormalization.
Some texts refer to this theorem as the Gram-Schmidt Orthogonalization Process, or just the Gram-Schmidt Process.
Some others use the term Gram-Schmidt Method.
== Sources ==
* 
* 
Category:Gram-Schmidt Orthogonalization
Gram-Schmidt Orthogonalization/Corollary 1

== Corollary to Gram-Schmidt Orthogonalization ==
Let $\struct {V, \innerprod \cdot \cdot}$ be an inner product space over $\R$ or $\C$.
Let $m \in \N_{>0}$ be a natural number.
Let $S = \set {v_n: n \le m}$ be a finite linearly independent subset of $V$. 
Then there exists an orthonormal subset $E = \set {e_n: n \le m}$ of $V$ such that:
:$\forall k \le m: \span \set {v_1, \ldots, v_k} = \span \set {e_1, \ldots, e_k}$
where $\span$ denotes linear span.
== Proof ==
Apply Gram-Schmidt Orthogonalization with $v_{m'} = v_m$ for $m' \ge m$.
== Sources ==
* : $\S 4.4$
Category:Gram-Schmidt Orthogonalization
Gram-Schmidt Orthogonalization/Corollary 2

== Theorem ==
Let $\struct {V, \innerprod \cdot \cdot}$ be an $n$-dimensional inner product space over $\R$ or $\C$.
Let $\tuple {v_1, \ldots, v_n}$ be any ordered basis for $V$.
Then there is an orthonormal ordered basis $\tuple {b_1, \ldots, b_n}$ satisfying the following conditions:
:$\forall k \in \set {1, \ldots, n} : \span \set {v_1, \ldots v_k} = \span \set {b_1, \ldots, b_k} $
== Proof ==
By the definition of basis, it follows that $\set{ v_1, \ldots, v_n }$ is a linearly independent subset of $V$.
From the Gram-Schmidt Orthogonalization:Corollary 1, it follows that there exists an orthonormal subset $\set {b_1, \ldots, b_n}$ of $V$ such that:
:$\forall k \in \set {1, \ldots, n}: \span \set {v_1, \ldots v_k} = \span \set {b_1, \ldots, b_k} $
where $\span$ denotes linear span.
From Orthogonal Set is Linearly Independent Set, it follows that $\set {b_1, \ldots, b_n}$ is a linearly independent subset of $V$.
By Sufficient Conditions for Basis of Finite Dimensional Vector Space, it follows that $\tuple {b_1, \ldots, b_n}$ is an ordered basis of $V$.
== Sources ==
* : $\S 2$: Riemannian Metrics. Definitions
Category:Vector Algebra
Category:Linear Algebra
Category:Gram-Schmidt Orthogonalization
Gram-Schmidt Orthogonalization/Scalar Product Space

== Theorem ==
Let $\struct {V, q}$ be an $n$-dimensional scalar product space
Suppose $\tuple {v_i}$ is a nondegenerate basis for $V$.
Then there is an orthonormal basis $\tuple {b_i}$ such that:
:$\ds \forall k \in \N_{> 0} : k \le n : \map \span {b_1, \ldots b_k} = \map \span {v_1, \ldots v_k}$
== Proof ==
== Sources ==
* : $\S 2$: Riemannian Metrics. Pseudo-Riemannian Metrics
Category:Scalar Product Spaces
Gram-Schmidt Orthogonalization/Scalar Product Space/Corollary

== Theorem ==
Let $\struct {V, q}$ be an $n$-dimensional scalar product space.
Let $V^*$ be the vector space dual to $V$.
Then there exists a basis $\tuple {\beta^i}$ for $V^*$ with respect to which $q$ has the expression:
:$q = \paren {\beta^1}^2 + \ldots + \paren {\beta^r}^2 - \paren {\beta^{r + 1}}^2 - \ldots - \paren {\beta^{r + s}}^2$
where:
:$r, s \in \N : r + s = n$.
== Proof ==
== Sources ==
* : $\S 2$: Riemannian Metrics. Pseudo-Riemannian Metrics
Category:Scalar Product Spaces
Graph (Graph Theory)/Examples/Arbitrary Example 2

== Example of Graph ==
This is an example of a graph presented in the style which uses circles for the vertices:
:
The edge set of this graph can be defined as:
:$E = \set {\set {n, m}: n + m = 4 \text { or } n + m = 7}$
== Sources ==
* : Chapter $1$: Preliminaries: $1.2$ Graphs and Trees
Category:Examples of Graphs
Graph Components are Equivalence Classes

== Theorem ==
The components of a graph are equivalence classes under the relation is connected to on the set of vertices.
== Proof ==
We have that Graph Connectedness is Equivalence Relation.
The result follows directly from the definition of component.
== Sources ==
* : $\S 2.3$: Connected Graphs: Problem $44$
Category:Graph Theory
Category:Examples of Equivalence Classes
Graph Connectedness is Equivalence Relation

== Theorem ==
Let $G = \struct {V, E}$ be a graph.
Let $\to$ denote the relation is connected to on the set $V$.
Then $\to$ is an equivalence relation.
== Proof ==
Let $u, v, w$ be arbitrary vertices of a graph $G$.
Checking in turn each of the criteria for equivalence:
=== Reflexive ===
By definition, all vertices are connected to themselves.
Hence $\to$ is reflexive.
=== Symmetric ===
Suppose $u \to v$.
By definition there exists a walk $W$ between $u$ and $v$.
Note that there is nothing in the definition of connectedness to insist that the walk has to be in a particular direction.
So by definition, if $u \to v$ then $v \to u$.
Hence $\to$ is symmetric.
=== Transitive ===
Suppose $u \to v$ and $v \to w$.
Let:
: $W_1 = \tuple {u, u_1, u_2, \ldots, u_{k - 1}, u_k, v}$ be a walk from $u$ to $v$
: $W_2 = \tuple {v, v_1, v_2, \ldots, v_{k - 1}, v_k, w}$ be a walk from $v$ to $w$.
Then $W = \tuple {u, u_1, u_2, \ldots, u_{k - 1}, u_k, v, v_1, v_2, \ldots, v_{k - 1}, v_k, w}$ is a walk from $u$ to $w$.
Hence $u \to w$, and so $\to$ is transitive.
Thus is connected to is an equivalence relation.
== Sources ==
* : $\S 2.3$: Connected Graphs: Problem $44$
Category:Connectedness (Graph Theory)
Category:Examples of Equivalence Relations
Graph Functor is Functor

== Definition ==
Let $\mathbf{Set}$ and $\mathbf{Rel}$ be the category of sets and the category of relations, respectively.
Let $G: \mathbf{Set} \to \mathbf{Rel}$ be the graph functor.
Then $G$ is a functor.
== Proof ==
For any set $X$, we have:
Thus $G$ preserves identity morphisms.
For mappings $f: X \to Y$ and $g: Y \to Z$, we have:
Hence $G$ is a functor.
== Sources ==
* : $\S 1.9$: Exercise $1 \,\text{(b)}$
Category:Category of Relations
Category:Category of Sets
Category:Functors
Graph Isomorphism is Equivalence Relation/Proof 1

== Theorem ==
== Proof ==
From the formal definitions:
=== Simple Graph ===
A (simple) graph $G$ is a non-empty set $V$ together with an antireflexive, symmetric relation $\RR$ on $V$.
=== Digraph ===
A digraph $D$ is a non-empty set $V$ together with an antireflexive relation $\RR$ on $V$.
=== Loop-graph ===
A loop-graph $P$ is a non-empty set $V$ together with a symmetric relation $\RR$ on $V$.
=== Loop-Digraph ===
A loop-digraph $D$ is a non-empty set $V$ together with a relation $\RR$ on $V$.
It can be seen from these definitions that all the above are relational structures with more or less restriction on the relation.
Hence the result from Relation Isomorphism is Equivalence Relation.
Category:Graph Isomorphism is Equivalence Relation