avewright/proofwiki-math huggingface dataset:
Theorem: Thales' Theorem

Let $A$ and $B$ be two points on opposite ends of the diameter of a circle.
Let $C$ be another point on the circle such that $C \ne A, B$.
Then the lines $AC$ and $BC$ are perpendicular to each other.
:400px

Proof:
Let $O$ be the center of $ACB$.
We have that $AO$, $BO$ and $CO$ are radii of the same circle.
Thus by definition:
:$AO = BO = CO$
Thus $\triangle AOC$ and $\triangle BOC$ are isosceles triangles.
From External Angle of Triangle equals Sum of other Internal Angles:
:$\angle COB = \angle ACO + \angle CAO$
Hence:
{{begin-eqn}}
{{eqn | l = \angle ACO
      | r = \angle CAO
      | c = Isosceles Triangle has Two Equal Angles
}}
{{eqn | ll= \leadsto
      | l = \angle COB
      | r = 2 \angle ACO
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \frac 1 2 \angle COB
      | r = \angle ACO
      | c = 
}}
{{end-eqn}}
Similarly, from External Angle of Triangle equals Sum of other Internal Angles:
:$\angle COA = \angle BCO + \angle CBO$
Hence:
{{begin-eqn}}
{{eqn | l = \angle BCO
      | r = \angle CBO
      | c = Isosceles Triangle has Two Equal Angles
}}
{{eqn | ll= \leadsto
      | l = \angle COA
      | r = 2 \angle BCO
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \frac 1 2 \angle COA
      | r = \angle BCO
      | c = 
}}
{{end-eqn}}
Therefore:
{{begin-eqn}}
{{eqn | l = \angle ACO + \angle BCO
      | r = \frac 1 2 \angle COB + \frac 1 2 \angle COA
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \angle ACB
      | r = \frac 1 2 \left({\angle COB + \angle COA}\right)
      | c = 
}}
{{end-eqn}}
But $\angle COB + \angle COA$ equals two right angles.
Hence $\angle ACB$ is a right angle.
{{qed}}
Theorem: Edge of Polyhedron has no Curvature

The edge of a polyhedron has zero curvature.

Proof:
File:Curvature.png
Let $X$ and $Y$ be two separate faces of a polyhedron separated by the edge $l$.
Let $P$ be a point on $X$ and let $Q$ be a point on $Y$.
The curvature inside an infinitesimal region $\delta a$ is given by the net angular displacement $\delta \theta$ a vector $v$ experiences as it is parallel transported along a closed path around $\delta a$.
The curvature is then given by:
:$R = \dfrac {\delta \theta} {\delta a}$
We must then prove that the vector $v$ experiences no net angular displacement as it is parallel transported from $P$ to $Q$ and back to $P$.
The two open curves $r$ and $s$ make a closed curve.
As the vector is parallel transported along the open curve $r$, it crosses the edge between the two faces $X$ and $Y$.
In doing so, it gains a finite angular displacement $\delta \theta_1$.
Then, when the vector is transported back along the open curve $s$, it gains another angular displacement $\delta \theta_2$.
Notice that because it is not being transported the other way (from $Y$ to $X$), the new angular displacement will be:
:$\delta \theta_2 = -\delta \theta_1$.
The curvature inside the region $\delta a$ is therefore given by:
{{begin-eqn}}
{{eqn | l = R
      | r = \frac {\delta \theta_1 + \delta \theta_2} {\delta a}
      | c = 
}}
{{eqn | r = \frac {\delta \theta_1 - \delta \theta_1} {\delta a}
      | c = 
}}
{{eqn | r = \frac 0 {\delta a}
      | c = 
}}
{{eqn | r = 0
      | c = 
}}
{{end-eqn}}
The result follows.
{{qed}}
Category:Differential Geometry
i5xdfev8t13dsp07igqp7g268zi8bsp
Theorem: Dot Product is Inner Product

The dot product is an inner product.

Proof:
Let $\mathbf u, \mathbf v \in \R^n$.
We will check the four defining properties of an inner product in turn.
Theorem: Factor Matrix in the Inner Product

Let $\mathbf u$ and $\mathbf v$ be $1 \times n$ column vectors.
Then:
:$\innerprod {A \mathbf u} {\mathbf v} = \innerprod {\mathbf u} {A^\intercal \mathbf v}$

Proof:
{{begin-eqn}}
{{eqn|l =\innerprod {A \mathbf u} {\mathbf v}
     |r =\paren {A \mathbf u}^\intercal \mathbf v
     |c = {{Defof|Dot Product}}
}}
{{eqn|r = \mathbf u^\intercal A^\intercal \mathbf v
     |c = Transpose of Matrix Product
}}
{{eqn|r = \innerprod {\mathbf u} {A^\intercal \mathbf v}
     |c = {{Defof|Dot Product}}
}}
{{end-eqn}}
{{Qed}}
Category:Vector Algebra
b8m6xs40jgcs7cnfcrkf0zztg4luxs4
Theorem: Empty Set Disjoint with Itself

The empty set is disjoint with itself:
:$\O \cap \O = \O$

Proof:
From Intersection with Empty Set, for all sets $S$, $S \cap \O = \O$.
The result follows from the definition of disjoint sets.
{{qed}}
Category:Empty Set
2amrsj1on7qtxcgdc0dpnhjrv8ftuxe
Theorem: Overflow Theorem

Let $F$ be a set of first-order formulas which has finite models of arbitrarily large size.
Then $F$ has an infinite model.

Proof:
For each $n$, let $\mathbf A_n$ be the formula:
:$\exists x_1 \exists x_2 \ldots \exists x_n: \paren {x_1 \ne x_2 \land x_1 \ne x_3 \land \ldots \land x_{n - 1} \ne x_n}$
Then $\mathbf A_i$ is true in a structure $\AA$ {{iff}} $\AA$ has at least $n$ elements.
Take:
:$\ds \Gamma := A \cup \bigcup_{i \mathop = 1}^\infty A_i$
Since $F$ has models of arbitrarily large size, every finite subset of $\Gamma$ is satisfiable.
From the Compactness Theorem, $\Gamma$ is satisfiable in some model $\MM$.
But since $\MM \models A_i$ for each $i$, $\MM$ must be infinite.
So $A$ has an infinite model.
{{qed}}
Theorem: Existence of Non-Standard Models of Arithmetic

There exist non-standard models of arithmetic.

Proof:
Let $P$ be the set of axioms of Peano arithmetic.
Let $Q = P \cup \left\{{\neg x = 0, \neg x = s0, \neg x = ss0, \ldots}\right\}$ where $x$ is a variable of the language.
Then each finite subset of $Q$ is satisfied by the standard model of arithmetic
Hence $Q$ is satisfiable by the Compactness theorem.
But any model satisfying $Q$ must assign $x$ to an element which cannot be obtained by iterating the successor operator on zero a finite number of times.
{{qed}}
{{MissingLinks}}
{{disambiguate|Definition:Model (Logic)}}
Category:Mathematical Logic
m3vzgmfsr7waas32t1qlq8ivfn035pc
Theorem: Pi is Irrational

Pi ($\pi$) is irrational.

Proof:
{{AimForCont}} $\pi$ is rational.
We establish a lemma:
=== Lemma ===
{{:Pi is Irrational/Proof 2/Lemma}}{{qed|lemma}}
We will use the definition of $A_n$ from the lemma.
Then we will deduce that $A_n$ is an integer for all $n$.
First we confirm by direct integration that $A_0$ and $A_1$ are integers:
{{begin-eqn}}
{{eqn | l = A_0
      | r = \int_0^\pi \sin x \rd x
      | c = 
}}
{{eqn | r = 2
      | c = Area under Arc of Sine Function
}}
{{end-eqn}}
and 
{{begin-eqn}}
{{eqn | l = A_1
      | r = q \int_0^\pi x \paren {\pi - x} \sin x \rd x
      | c = 
}}
{{eqn | r = q \paren {\pi \int_0^\pi x \sin x \rd x - \int_0^\pi x^2 \sin x \rd x }
      | c = Linear Combination of Integrals
}}
{{eqn | r = q \paren {\pi \bigintlimits {- x \cos x + \sin x} 0 \pi - \bigintlimits {- x^2 \cos x + 2 x \sin x + 2 \cos x} 0 \pi }
      | c = Primitive of $x^n \sin a x$
}}
{{eqn | r = q \paren {\pi^2 - \pi^2 + 2 + 2}
      | c = Cosine of $\pi$, {{cos|0}}, Sine of $\pi$, {{sin|0}}
}}
{{eqn | r = 4 q
      | c = 
}}
{{end-eqn}}
Suppose $A_{k - 2}$ and $A_{k - 1}$ are integers. 
By our lemma:
:$A_k = \paren {4 n - 2} q A_{k - 1} - p^2 A_{k - 2}$
As $n$, $p$ and $q$ are all integers {{hypothesis}}, $A_k$ is also an integer.
So $A_n$ is an integer for all $n$ by Second Principle of Mathematical Induction.
{{qed|lemma}}
Let $x \in \closedint 0 \pi$.
From Shape of Sine Function and Real Sine Function is Bounded, we have:
:$0 \le \sin x \le 1$
{{qed|lemma}}
Let:
{{begin-eqn}}
{{eqn | l = \map f x
      | r = x \paren {\pi - x}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map {f'} x
      | r = \pi - 2 x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 0
      | r = \pi - 2 x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x
      | r = \dfrac \pi 2
      | c = 
}}
{{end-eqn}}
From the Interior Extremum Theorem, $\map f x$ is a maximum or minimum at $x = \dfrac \pi 2$.
Then also:
:$\map f 0 = \map f \pi = 0$
and:
:$\map f {\dfrac \pi 2} = \dfrac {\pi^2} 4$
So on $\closedint 0 \pi$, $x = \dfrac \pi 2$ is in fact a maximum for $x \paren {\pi - x}$.
So we have:
Hence it follows that:
:$0 \le x \paren {\pi - x} \le \dfrac {\pi^2} 4$
{{qed|lemma}}
Since $A_n$ is clearly positive and the length of the interval is $\pi$ and the integrand is bounded at $\paren {\pi^2 / 4}^n$, from Darboux's Theorem, we have:
:$0 < A_n < \pi \times \dfrac {q^n} {n!} \times \paren {\pi^2 / 4}^n$
From Power over Factorial:
:$\ds \lim_{n \mathop \to \infty} \frac {\paren {q \pi^2 / 4}^n} {n!} = 0$
It follows from the Squeeze Theorem that:
:$\ds \lim_{n \mathop \to \infty} A_n = 0$
Hence for sufficiently large $n$, $A_n$ is strictly between $0$ and $1$.
This contradicts the deduction that $A_n$ is an integer.
This depends on our supposition that $\pi$ is a rational number,
Hence by Proof by Contradiction it follows that $\pi$ is irrational.
{{qed}}
Theorem: Pi is Irrational

Pi ($\pi$) is irrational.

Proof:
From Rational Points on Graph of Sine Function, the only rational point on the graph of the sine function in the real Cartesian plane $\R^2$:
:$f := \left\{ {\left({x, y}\right) \in \R^2: y = \sin x}\right\}$
is the point $\left({0, 0}\right)$.
But $\left({\pi, 0}\right)$ is also on $f$.
Hence $\pi$ cannot be rational.
{{qed}}
Theorem: Properties of Hadamard Product

Let $\map {\MM_S} {m, n}$ be a $m \times n$ matrix space over $S$ over an algebraic structure $\struct {S, \cdot}$.
Let $\mathbf A, \mathbf B \in \map {\MM_S} {m, n}$.
Let $\mathbf A \circ \mathbf B$ be defined as the Hadamard product of $\mathbf A$ and $\mathbf B$.
The operation $\circ$ of Hadamard product satisfies the following properties:
:$\circ$ is closed on $\map {\MM_S} {m, n}$ {{iff}} $\cdot$ is closed on $\struct {S, \cdot}$
:$\circ$ is associative on $\map {\MM_S} {m, n}$ {{iff}} $\cdot$ is associative on $\struct {S, \cdot}$
:$\circ$ is commutative on $\map {\MM_S} {m, n}$ {{iff}} $\cdot$ is commutative on $\struct {S, \cdot}$.

Proof:
=== Closure of Hadamard Product ===
{{:Closure of Hadamard Product}}
Theorem: Matrix Space is Module

Let $\struct {R, +, \circ}$ be a ring.
Let $\mathbf A = \sqbrk a_{m n}$ be an $m \times n$ matrix over $\struct {R, +, \circ}$.
Then the matrix space $\map {\MM_R} {m, n}$ of all $m \times n$ matrices over $R$ is a module.

Proof:
This follows as $\map {\MM_R} {m, n}$ is a direct instance of the module given in the module of all mappings, where $\map {\MM_R} {m, n}$ is the $R$-module $R^{\closedint 1 m \times \closedint 1 n}$.
The $S$ of that example is the set $\closedint 1 m \times \closedint 1 n$, while the $G$ of that example is the $R$-module $R$.
Let $\sqbrk a_{i j}$ and $\sqbrk b_{i j}$ be the $\tuple{i, j}$th element of $m \times n$ matrices $\mathbf A$ and $\mathbf B$ respectively.
Let $\lambda$ and $\mu$ be arbitrary elements of $R$.
We have for all $i \in \closedint 1 m$, $j \in \closedint 1 n$, by egregious abuse of notation:
{{begin-eqn}}
{{eqn | l = \lambda \circ \paren {\mathbf A + \mathbf B}
      | r = \lambda \circ \paren {a_{i j} + b_{i j} }
      | c = {{Defof|Matrix Entrywise Addition over Ring}}
}}
{{eqn | r = \lambda \circ a_{i j} + \lambda \circ b_{i j}
      | c = {{Ring-axiom|D}}
}}
{{eqn | r = \lambda \circ \mathbf A + \lambda \circ \mathbf B
      | c = hence fulfilling {{Module-axiom|1}}
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \paren {\lambda + \mu} \circ \mathbf A
      | r = \paren {\lambda + \mu} \circ a_{i j}
      | c = {{Defof|Matrix Scalar Product over Ring}}
}}
{{eqn | r = \lambda \circ a_{i j} + \mu \circ a_{i j}
      | c = {{Ring-axiom|D}}
}}
{{eqn | r = \lambda \circ \mathbf A + \mu \circ \mathbf A
      | c = hence fulfilling {{Module-axiom|2}}
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \paren {\lambda \circ \mu} \circ \mathbf A
      | r = \paren {\lambda \circ \mu} \circ a_{i j}
      | c = {{Defof|Matrix Scalar Product over Ring}}
}}
{{eqn | r = \lambda \circ \paren {\mu \circ a_{i j} }
      | c = {{Ring-axiom|M1}}
}}
{{eqn | r = \lambda \circ \paren {\mu \circ \mathbf A}
      | c = hence fulfilling {{Module-axiom|3}}
}}
{{end-eqn}}
{{qed}}
Theorem: Graph Isomorphism is Equivalence Relation

Graph isomorphism is an equivalence relation.

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.
{{qed}}
Theorem: Graph Isomorphism is Equivalence Relation

Graph isomorphism is an equivalence relation.

Proof:
In the following, let:
{{begin-eqn}}
{{eqn | l = G_1
      | r = \struct {\map V {G_1}, \map E {G_1} }
}}
{{eqn | l = G_2
      | r = \struct {\map V {G_2}, \map E {G_2} }
}}
{{eqn | l = G_3
      | r = \struct {\map V {G_3}, \map E {G_3} }
}}
{{end-eqn}}
be arbitrary graphs.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
The identity mapping on $\map V {G_1}$ is a bijection that maps each vertex to itself.
This is seen to preserve adjacency.
Thus graph isomorphism preserves reflexivity.
{{qed|lemma}}
=== Symmetry ===
Let $G_1$ be isomorphic to $G_2$
Then there exists an isomorphism $\phi: \map V {G_1} \to \map V {G_2}$ from $\map V {G_1}$ to $\map V {G_2}$.
Let its inverse $\phi^{-1}: \map V {G_2} \to \map V {G_1}$ be defined by:
:$\map {\phi^{-1} } {v_2} = v_1 \iff \map \phi {v_1} = v_2$
By Inverse of Bijection is Bijection, $\phi^{-1}$ is a bijection.
Let $u_2, v_2 \in \map V {G_2}$ such that $\map {\phi^{-1} } {u_2} = u_1$ and $\map {\phi^{-1} } {v_2} = v_1$.
Then:
{{begin-eqn}}
{{eqn | l = \map \phi {u_1}
      | r = u_2
}}
{{eqn | l = \map \phi {v_1}
      | r = v_2
}}
{{end-eqn}}
So $u_2$ and $v_2$ are adjacent {{iff}} $\map \phi {u_1}$ and $\map \phi {v_1}$ are adjacent.
Because $G_1$ is isomorphic to $G_2$, $\map \phi {u_1}$ and $\map \phi {v_1}$ are adjacent {{iff}} $u_1 = \map {\phi^{-1} } {u_2}$ and $v_1 = \map {\phi^{-1} } {v_2}$ are adjacent.
So $u_2$ and $v_2$ are adjacent {{iff}} $u_1 = \map {\phi^{-1} } {u_2}$ and $v_1 = \map {\phi^{-1} } {v_2}$ are adjacent.
That is, $G_2$ is isomorphic to $G_1$
Thus graph isomorphism preserves symmetry.
{{qed|lemma}}
=== Transitivity ===
Let $G_1$ be isomorphic to $G_2$ and $G_2$ be isomorphic to $G_3$.
Then there exist isomorphisms:
:$\alpha: \map V {G_1} \to \map V {G_2}$ from $\map V {G_1}$ to $\map V {G_2}$
:$\beta: \map V {G_2} \to \map V {G_3}$ from $\map V {G_2}$ to $\map V {G_3}$.
Consider the composite mapping $\beta \circ \alpha$.
From Composite of Bijections is Bijection, $\beta \circ \alpha$ is a bijection from $\map V {G_1}$ to $\map V {G_3}$.
Let $u_1, v_1 \in \map V {G_1}$.
Let $\map \alpha {u_1} = u_2$ and $\map \alpha {v_1} = v_2$.
Let $\map \beta {u_2} = u_3$ and $\map \beta {v_2} = v_3$.
We have that $\alpha$ and $\beta$ are isomorphisms.
So:
:$u_1$ and $v_1$ are adjacent {{iff}} $\map \alpha {u_1} = u_2$ and $\map \alpha {v_1} = v_2$ are adjacent
:$u_2$ and $v_2$ are adjacent {{iff}} $\map \beta {u_2} = u_3$ and $\map \beta {v_2} = v_3$ are adjacent.
Thus:
:$u_1$ and $v_1$ are adjacent {{iff}} $\map \beta {\map \alpha {u_1} } = u_3$ and $\map \beta {\map \alpha {v_1} } = v_3$ are adjacent.
That is, {{iff}} $\map {\paren {\beta \circ \alpha} } {u_1} = u_3$ and $\map {\paren {\beta \circ \alpha} } {v_1} = v_3$ are adjacent.
Thus it has been demonstrated that $\beta \circ \alpha$ is an isomorphism.
Thus graph isomorphism has been shown to preserve transitivity.
{{qed|lemma}}
Graph isomorphism has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
{{qed}}
Theorem: Relation Isomorphism is Equivalence Relation

Relation isomorphism is an equivalence relation.

Proof:
Let $\struct {S_1, \RR_1}$, $\struct {S_2, \RR_2}$ and $\struct {S_3, \RR_3}$ be relational structures.
Let $S \cong T$ denote the relation that $S$ is (relation) isomorphic to $T$.
Checking in turn each of the criteria for equivalence:
Theorem: Vertex Condition for Isomorphic Graphs

Let $G_1$ and $G_2$ be isomorphic graphs.
Then the degrees of the vertices of $G_1$ are exactly the same as the degrees of the vertices of $G_2$.

Proof:
Let $\phi: \map V {G_1} \to \map V {G_2}$ be an isomorphism.
Let $u \in \map V {G_1}$ be an arbitrary vertex of $G_1$ such that $\map \phi u = v \in \map V {G_2}$.
Let $\map {\deg_{G_1} } u = n$.
We need to show that $\map {\deg_{G_2} } v = n$.
As $\map {\deg_{G_1} } u = n$, there exist $u_1, u_2, \ldots, u_n \in \map V {G_1}$ which are adjacent to $u$.
Every other vertex of $G_1$ is ''not'' adjacent to $u$.
Let $\map \phi {u_i} = v_i$ for $1, 2, \ldots, n$.
Because $\phi$ is an isomorphism, each of the vertices $v_1, v_2, \ldots, v_n \in \map V {G_2}$ are adjacent to $v$.
Similarly, every other vertex of $G_2$ is ''not'' adjacent to $v$.
Thus $\map {\deg_{G_2} } v = n$.
This applies to all vertices $u \in  \map V {G_1}$.
Hence the result.
{{qed}}
Theorem: Dirichlet's Box Principle

Let $S$ be a finite set whose cardinality is $n$.
Let $S_1, S_2, \ldots, S_k$ be a partition of $S$ into $k$ subsets.
Then:
:at least one subset $S_i$ of $S$ contains at least $\ceiling {\dfrac n k}$ elements
where $\ceiling {\, \cdot \,}$ denotes the ceiling function.

Proof:
{{AimForCont}} no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements.
Then the maximum number of elements of any $S_i$ would be $\ceiling {\dfrac n k} - 1$.
So the total number of elements of $S$ would be no more than $k \paren {\ceiling {\dfrac n k} - 1} = k \ceiling {\dfrac n k} - k$.
There are two cases:
:$n$ is divisible by $k$
:$n$ is not divisible by $k$.
Suppose $k \divides n$.
Then $\ceiling {\dfrac n k} = \dfrac n k$ is an integer and:
:$k \ceiling {\dfrac n k} - k = n - k$
Thus:
:$\ds \card S = \sum_{i \mathop = 1}^k \card {S_i} \le n - k < n$
This contradicts the fact that $\card S = n$.
Hence our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.
Next, suppose that $k \nmid n$.
Then:
:$\card S = k \ceiling {\dfrac n k} - k < \dfrac {k \paren {n + k} } k - k = n$
and again this contradicts the fact that $\card S = n$.
In the same way, our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.
Hence, by Proof by Contradiction, there has to be at least $\ceiling {\dfrac n k}$ elements in at least one $S_i \subseteq S$.
{{qed}}
Theorem: Graph Components are Equivalence Classes

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.
{{qed}}
Theorem: Graph Connectedness is Equivalence Relation

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:
Theorem: Condition for Edge to be Bridge

Let $G = \struct {V, E}$ be a connected graph.
Let $e \in E$ be an edge of $G$.
Then $e$ is a bridge {{iff}} $e$ does not lie on any circuit of $G$.

Proof:
Let $G - e$ denote the edge deletion of $e$ from $G$.
Theorem: Characteristics of Traversable Graph

A finite loop-multigraph is '''traversable''' {{iff}} it is connected and no more than two vertices are odd.
An Eulerian trail which is not an Eulerian circuit must start and end at an odd vertex.

Proof:
{{improve|this can be presented in a neater way}}
Let $G$ be a graph.
Suppose all the vertices are even, that is, there are no odd vertices.
Then $G$ is Eulerian, and the result holds.
Similarly, by the same result, if $G$ is Eulerian, it is by definition traversable.
So the question of graphs all of whose vertices are even is settled.
Theorem: Odd Order Complete Graph is Eulerian

Let $K_n$ be the complete graph of $n$ vertices.
Then $K_n$ is Eulerian {{iff}} $n$ is odd.
If $n$ is even, then $K_n$ is traversable iff $n = 2$.

Proof:
From the definition, the complete graph $K_n$ is $n-1$-regular.
That is, every vertex of $K_n$ is of degree $n-1$.
Suppose $n$ is odd. Then $n-1$ is even, and so $K_n$ is Eulerian.
Suppose $n$ is even. Then $n-1$ is odd.
Hence for $n \ge 4$, $K_n$ has more than $2$ odd vertices and so can not be traversable, let alone Eulerian.
If $n = 2$, then $K_n$ consists solely of two odd vertices (of degree $1$).
Hence, by Characteristics of Traversable Graph (or trivially, by inspection), $K_2$ has an Eulerian trail, and so is traversable (although not Eulerian).
{{qed}}
Theorem: Odd Vertices Determines Edge-Disjoint Trails

Let $G$ be a loop-multigraph with $2 n$ odd vertices, $n > 0$.
Then $G$ has $n$ edge-disjoint trails such that every edge of $G$ is contained in one of these trails.
Each of these trails starts and ends on an odd vertex.

Proof:
We prove this result by induction:
For all $n \in \N_{>0}$, let $\map P N$ be the proposition:
:if $G$ has $2 n$ odd vertices, it consists entirely of $n$ edge-disjoint trails, each starting and ending on an odd vertex.
First note that from {{Corollary|Handshake Lemma}}, no graph can have an odd number of odd vertices.
Theorem: Number of Edges of Regular Graph

An $r$-regular graph of order $n$ is of size $\dfrac {n r} 2$.

Proof:
The size of a $r$-regular graph is its number of edges.
The order of a $r$-regular graph is its number of vertices.
The degree of each vertex of an $r$-regular graph is $r$.
Hence the total of all the degrees of an $r$-regular graph of order $n$ is $nr$.
The result follows directly from the Handshake Lemma.
{{qed}}
Category:Regular Graphs
3c712ia7q15uhflusq9w8y87en80nkh
Theorem: Graph is Bipartite iff No Odd Cycles

Let $G$ be an undirected graph.
Then $G$ is bipartite {{iff}} it has no odd cycles.

Proof:
=== Sufficient Condition ===
Let $G = \struct {V, E}$ be bipartite.
So, let $V = A \cup B$ such that $A \cap B = \O$ and that all edges $e \in E$ are such that $e$ is of the form $\set {a, b}$ where $a \in A$ and $b \in B$.
(This is the definition of a bipartite graph.)
Suppose $G$ has (at least) one odd cycle $C$.
Let the length of $C$ be $n$.
Let $C = \tuple {v_1, v_2, \ldots, v_n, v_1}$.
{{WLOG}}, let $v_1 \in A$. It follows that $v_2 \in B$ and hence $v_3 \in A$, and so on.
Hence we see that $\forall k \in \set {1, 2, \ldots, n}$, we have:
:<nowiki>$v_k \in \begin{cases}
A : & k \text{ odd} \\
B : & k \text{ even}
\end{cases}$</nowiki>
But as $n$ is odd, $v_n \in A$.
But $v_1 \in A$, and $v_n v_1 \in C_n$.
So $v_n v_1 \in E$ which contradicts the assumption that $G$ is bipartite.
Hence if $G$ is bipartite, it has no odd cycles.
{{qed|lemma}}
Theorem: Ore's Theorem

Let $G = \struct {V, E}$ be a simple graph of order $n \ge 3$.
Let $G$ be an Ore graph, that is:
:For each pair of non-adjacent vertices $u, v \in V$:
::$(1): \quad \deg u + \deg v \ge n$
Then $G$ is Hamiltonian.

Proof:
From Ore Graph is Connected it is not necessary to demonstrate that $G$ is connected.
{{AimForCont}} it were possible to construct a graph that fulfils condition $(1)$ which is not Hamiltonian.
For a given $n \ge 3$, let $G$ be the graph with the most possible edges such that $G$ is non-Hamiltonian which satisfies $(1)$.
Although it does not contain a Hamilton cycle, $G$ has to contain a Hamiltonian path $\tuple {v_1, v_2, \ldots, v_n}$.
Otherwise it would be possible to add further edges to $G$ without making $G$ Hamiltonian.
Since $G$ is not Hamiltonian, $v_1$ is not adjacent to $v_n$, otherwise $\tuple {v_1, v_2, \ldots, v_n, v_1}$ would be a Hamilton cycle.
By $(1)$, we have that:
:$\deg v_1 + \deg v_n \ge n$
By the Pigeonhole Principle, for some $i$ such that $2 \le i \le n - 1$, $v_i$ is adjacent to $v_1$, and $v_{i - 1}$ is adjacent to $v_n$.
But the cycle $\tuple {v_1, v_2, \ldots, v_{i - 1}, v_n, v_{n - 1}, \ldots, v_i, v_1}$ is then a Hamilton cycle.
So $G$ is Hamiltonian after all.
{{Qed}}