avewright/proofwiki-math huggingface dataset:
Theorem: Set of Transpositions is not Subgroup of Symmetric Group

Let $S$ be a finite set with $n$ elements such that $n > 2$.
Let $G = \struct {\map \Gamma S, \circ}$ denote the symmetric group on $S$.
Let $H \subseteq G$ denote the set of all transpositions of $S$ along with the identity mapping which moves no elements of $S$.
Then $H$ does not form a subgroup of $G$.

Proof:
First it is noted that $H \subseteq G$, and that the identity mapping is an element of $H$.
Hence to demonstrate that $H$ is a subgroup of $G$, one may use the Two-Step Subgroup Test.
Let $\phi \in H$ be a transposition.
Then from Transposition is Self-Inverse, $\phi^{-1} \in H$.
So $H$ is closed under inversions.
Let $a, b, c \in S$.
Let $\pi, \phi \in H$ such that:
:$\pi = \tuple {a \ b}$
:$\phi = \tuple {b \ c}$
Then by inspection:
:$\phi \circ \pi = \tuple {a \ c \ b}$
Thus $\phi \circ \pi$ is a $3$-cycle and so not a transposition.
Hence $H$ is not closed under composition.
So, by the Two-Step Subgroup Test, $H$ is not a subgroup of $G$.
{{Qed}}
Theorem: Positive Real Axis forms Subgroup of Complex Numbers under Multiplication

Let $S$ be the subset of the set of complex numbers $\C$ defined as:
:$S = \set {z \in \C: z = x + 0 i, x > 0}$
That is, let $S$ be the positive real axis of the complex plane.
Then the algebraic structure $\struct {S, \times}$ is a subgroup of the multiplicative group of complex numbers $\struct {\C_{\ne 0}, \times}$.

Proof:
We have that $S$ is the same thing as $\R_{>0}$, the set of strictly positive real numbers:
:$\R_{>0} = \set {x \in \R: x > 0}$
From Strictly Positive Real Numbers under Multiplication form Uncountable Abelian Group, $\struct {S, \times}$ is a group.
Hence as $S$ is a group which is a subset of $\struct {\C_{\ne 0}, \times}$, it follows that $\struct {S, \times}$ is a subgroup of $\struct {\C_{\ne 0}, \times}$.
{{qed}}
Theorem: Homomorphism from Reals to Circle Group/Corollary

Let $\struct {\R, +}$ be the additive group of real numbers.
Let $\struct {C_{\ne 0}, \times}$ be the multiplicative group of complex numbers.
Let $\phi: \struct {\R, +} \to \struct {C_{\ne 0}, \times}$ be the mapping defined as:
:$\forall x \in \R: \map \phi x = \cos x + i \sin x$
Then $\phi$ is a (group) homomorphism.

Proof:
By Euler's Identity, $\phi$ can also be expressed as:
:$\forall x \in \R: \map \phi x = e^{i x}$
From Homomorphism from Reals to Circle Group, $\phi$ is a homomorphism from $\struct {\R, +}$ to the circle group $\struct {K, \times}$.
From Circle Group is Infinite Abelian Group, we note that $\struct {K, \times}$ is a subgroup of the multiplicative group of complex numbers.
{{qed}}
Theorem: Equivalence of Definitions of Closed Set in Normed Vector Space

{{TFAE|def = Closed Set in Normed Vector Space|view = Closed Set|context = Normed Vector Space|contextview = Normed Vector Spaces}}
Let $V = \struct {X, \norm {\, \cdot \,}}$ be a normed vector space.
Let $F \subseteq X$.

Proof:
Let $\sequence {x_n}_{n \mathop \in \N}$ be a sequence in $F$ with a limit point $x$ in $X$.
Theorem: Cosets of Positive Reals in Multiplicative Group of Complex Numbers

Let $S$ be the positive real axis of the complex plane:
:$S = \set {z \in \C: z = x + 0 i, x \in \R_{>0} }$
Consider the algebraic structure $\struct {S, \times}$ as a subgroup of the multiplicative group of complex numbers $\struct {\C_{\ne 0}, \times}$.
The cosets of $\struct {S, \times}$ are the sets of the form:
:$\set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$ for some $\theta \in \hointr 0 {2 \pi}$
That is, the sets of all complex numbers with a constant argument.

Proof:
Let $z_0 \in \C_{\ne 0}$.
Write $z_0 = r_0 e^{i \theta}$, where $r_0 > 0$ and $\theta \in \hointr 0 {2 \pi}$.
We will show that:
:$z_0 S = \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$
Pick any $w \in z_0 S$.
Then there exists some $x \in S$ such that $w = z_0 x$.
Note that $x \in \R_{>0}$ and $r_0 x \in \R_{>0}$.
Thus:
:$w = z_0 x = r_0 x e^{i \theta} \in \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$
This shows that:
:$z_0 S \subseteq \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$
Pick any $w \in \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$.
Write $w = r e^{i \theta}$, where $r \in \R_{>0}$.
Note that $\dfrac r {r_0} \in \R_{>0}$.
Then:
:$w = \paren {\dfrac r {r_0}} r_0 e^{i \theta} = \paren {\dfrac r {r_0}} z_0 \in z_0 S$
This shows that:
:$z_0 S \supseteq \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$
By definition of set equality:
:$z_0 S = \set {z \in \C: \exists r \in \R_{>0}: z = r e^{i \theta}}$
{{qed}}
Theorem: Morphism from Multiplicative Group of Complex Numbers to Unit Circle

Let $\struct {\C_{\ne 0}, \times}$ denote the multiplicative group of complex numbers.
Let $f: \C_{\ne 0} \to \C_{\ne 0}$ be the mapping defined as:
:$\forall z \in \C_{\ne 0}: \map f z = \dfrac z {\cmod z}$
where $\cmod z$ denotes the modulus of $z$.
Then $f$ is an endomorphism on $\struct {\C_{\ne 0}, \times}$ whose kernel is the positive real axis:
:$\set {z \in \C: z = x + 0 i, x \in \R_{>0} }$
and whose image is the unit circle:
:$\set {z \in \C: \cmod z = 1}$

Proof:
{{ProofWanted|Straightforward but tedious}}
Theorem: Rational Numbers are Dense Subfield of P-adic Numbers

Let $p$ be a prime number.
Let $\norm {\,\cdot\,}^{\Q}_p$ be the p-adic norm on the rational numbers $\Q$.
Let $\struct {\Q_p, \norm {\,\cdot\,}_p}$ be the $p$-adic numbers.
Let $\phi: \Q \to \Q_p$ be the mapping defined by:
:$\map \phi r = \eqclass {r, r, r, \dotsc} {}$
where $\eqclass {r, r, r, \dotsc} {}$ is the left coset in $\Q_p$ that contains the constant sequence $\sequence {r, r, r, \dotsc}$.
Then:
:$\struct{\Q, \norm {\,\cdot\,}^{\Q}_p }$ is isometrically isomorphic to $\map \phi \Q$ which is a dense subfield of $\Q_p$.
That is, $\struct{\Q, \norm {\,\cdot\,}^{\Q}_p }$ can be identified as a dense subfield of $\struct {\Q_p, \norm {\,\cdot\,}_p}$ and $\norm {\,\cdot\,}_p$ as an extension of $\norm {\,\cdot\,}^\Q_p$.

Proof:
From P-adic Numbers form Completion of Rational Numbers with P-adic Norm:
:$\struct {\Q_p, \norm {\,\cdot\,}_p}$ is a completion of $\struct {\Q, \norm {\,\cdot\,}^\Q_p}$
From Embedding Division Ring into Quotient Ring of Cauchy Sequences:
:the mapping $\phi: \Q \to \Q_p$ is a distance-preserving monomorphism.
From Normed Division Ring is Dense Subring of Completion:
:$\struct {\Q, \norm {\, \cdot \,}^\Q_p }$ is isometrically isomorphic to $\struct {\map \phi \Q, \norm {\, \cdot \,}_p }$ which is a dense subfield of $\struct {\Q_p, \norm {\, \cdot \,}_p }$.
{{qed}}
Category:Rational Numbers
Category:Everywhere Dense
Category:P-adic Number Theory
sn91o995uyvplt65own472orfrah0yy
Theorem: Graph is 0-Regular iff Edgeless

Let $G$ be a graph.
Then $G$ is $0$-regular graph {{iff}} $G$ is edgeless.

Proof:
=== Sufficient Condition ===
Let $G$ be an edgeless graph.
By definition of edgeless graph, $G$ has no edges.
That means every vertex of $G$ is incident with no edges.
That is, every vertex of $G$ is of degree $0$.
Hence the result, by definition of $0$-regular graph.
{{qed|lemma}}
Theorem: Edgeless Graph is Bipartite

Let $N_n$ denote the edgeless graph with $n$ vertices.
Then $N_n$ is a bipartite graph.

Proof:
Because $N_n$ has no edges, it has no cycles longer than $0$.
Thus in particular, it has no odd cycles.
The result follows from Graph is Bipartite iff No Odd Cycles.
{{qed}}
Category:Edgeless Graphs
Category:Bipartite Graphs
onj0q7fygjn9c7y8vyoibcwtir8973h
Theorem: Edgeless Graph of Order n has n Components

Let $N_n$ denote the edgeless graph with $n$ vertices.
Then $N_n$ has $n$ components.

Proof:
Because there are $n$ vertices in $N_n$, it cannot have more than $n$ components.
{{AimForCont}} $N_n$ has fewer than $n$ components.
That would mean that at least $2$ vertices of $N_n$ are connected.
But to be connected, they need to be joined by at least one edge.
But that contradicts the fact that $N_n$ has no edges.
Hence by Proof by Contradiction it is not possible for $N_n$ to have fewer than $n$ components.
Thus it must be the case that $N_n$ has exactly $n$ components.
{{qed}}
Category:Edgeless Graphs
i1btb0ilnm3j7habcqpc9vlv4f7gamr
Theorem: Complete Graph of Order 1 is Edgeless

The complete graph $K_1$ of order $1$ is the edgeless graph $N_1$.

Proof:
By definition, $K_1$ has $1$ vertex.
From Complete Graph is Regular, $K_1$ is $0$-regular.
Hence the result from Graph is 0-Regular iff Edgeless.
{{qed}}
Category:Edgeless Graphs
Category:Complete Graphs
oyi3m2zbnw1gysum6opypbdjzd67alx
Theorem: Complement of Complete Graph is Edgeless Graph

Let $K_n$ denote the complete graph of order $n$.
Then the complement of $K_n$ is the $n$-edgeless graph $N_n$.

Proof:
By definition of complete graph, each vertex of $K_n$ is adjacent to every other vertex of $K_n$.
Let $\overline {K_n}$ denote the complement of $K_n$.
Let $v$ be a vertex of $\overline {K_n}$.
By definition of complement, $v$ is adjacent to all the vertices of $\overline {K_n}$ that it is not in $K_n$.
But that means $v$ is adjacent to no vertices of $\overline {K_n}$.
That means $v$ is a $0$-regular graph.
The result follows from Graph is 0-Regular iff Edgeless.
{{qed}}
Theorem: Edgeless Graph of Order 1 is Tree

Let $N_1$ denote the edgeless graph with $1$ vertex.
Then $N_1$ is a tree.

Proof:
By definition, a tree is a simple connected graph with no circuits.
$N_1$ is trivially connected graph.
As $N_1$ is edgeless, it has no edges.
But a circuit is a closed trail with at least one edge.
Hence the result.
{{qed}}
Category:Edgeless Graphs
Category:Tree Theory
nl2aycgpr91he895hzgrfs94keg40mt
Theorem: Edgeless Graph of Order Greater than 1 is Forest

Let $N_n$ denote the edgeless graph with $n$ vertices such that $n > 1$.
Then $N_n$ is a forest.

Proof:
By definition, a '''forest''' is a simple graph whose components are all trees.
From Edgeless Graph of Order n has n Components $N_n$ has as many components as it has vertices.
Each of those vertices is an instance of $N_1$, the edgeless graph with $1$ vertex.
The result follows from Edgeless Graph of Order 1 is Tree.
{{qed}}
Category:Edgeless Graphs
Category:Forests
r75yjqg1zlbbdptu1zc8s9gp9crist9
Theorem: Size of Complete Graph

Let $K_n$ denote the complete graph of order $n$ where $n \ge 0$.
The size of $K_n$ is given by:
:$\size {K_n} = \dfrac {n \paren {n - 1} } 2$

Proof:
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\size {K_n} = \dfrac {n \paren {n - 1} } 2$
First we explore the degenerate case $\map P 0$:
{{begin-eqn}}
{{eqn | l = \size {K_0}
      | r = 0
      | c = as $K_0$ is the null graph
}}
{{eqn | r = \dfrac {0 \paren {0 - 1} } 2
      | c = 
}}
{{end-eqn}}
Thus $\map P 0$ is seen to hold.
Theorem: Field Operations of P-adic Numbers

Let $p$ be a prime number.
Let $\norm {\,\cdot\,}_p$ be the p-adic norm on the rationals $\Q$.
Let $\struct {\Q_p, \norm {\,\cdot\,}_p}$ be the $p$-adic numbers.
That is, $\Q_p$ is the quotient ring $\CC \, \big / \NN$ where:
:$\CC$ denotes the commutative ring of Cauchy sequences over $\struct {\Q, \norm {\,\cdot\,}_p}$
:$\NN$ denotes the set of null sequences in $\struct {\Q, \norm {\,\cdot\,}_p}$.
Then $\Q_p$ is a field and the field operations are defined by:
:$+ : \quad \forall \sequence {x_n} + \NN, \sequence {y_n} + \NN \in \CC \, \big / \NN$:
:::$\quad \paren {\sequence {x_n} + \NN} + \paren {\sequence {y_n} + \NN} = \sequence {x_n + y_n} + \NN$
:$\circ : \quad \forall \sequence {x_n} + \NN, \sequence {y_n} + \NN \in \CC \, \big / \NN$: 
:::$\quad \paren {\sequence {x_n} + \NN} \paren {\sequence {y_n} + \NN} = \sequence {x_n y_n} + \NN$

Proof:
By {{Corollary|Cauchy Sequences form Ring with Unity}}, $\CC$ is a commutative ring of Cauchy sequences with the ring operations defined by:
:$+ : \quad \forall \sequence {x_n}, \sequence {y_n} \in \CC$:
:::$\quad \sequence {x_n} + \sequence {y_n} = \sequence {x_n + y_n}$
:$\circ : \quad \forall \sequence {x_n}, \sequence {y_n} \in \CC$:
:::$\quad \sequence {x_n} \circ \sequence {y_n} = \sequence {x_n y_n}$
By {{Corollary|Null Sequences form Maximal Left and Right Ideal|1}}, $\NN$ is a maximal ideal of $\CC$. 
By {{Corollary|Quotient Ring of Cauchy Sequences is Division Ring|1}}, the quotient ring $\Q_p = \CC \big / \NN$ is a field with field operations defined by:
:$+ :\quad \forall \sequence {x_n} + \NN, \sequence {y_n} + \NN \in \CC \, \big / \NN$:
:::$\quad \paren {\sequence {x_n} + \NN} + \paren {\sequence {y_n} + \NN} = \paren {\sequence {x_n} + \sequence {y_n} } + \NN$
:$\circ :\quad \forall \sequence {x_n} + \NN, \sequence {y_n} + \NN \in \CC \, \big / \NN$: 
:::$\quad \paren {\sequence {x_n} + \NN} \paren {\sequence {y_n} + \NN} = \paren {\sequence {x_n} \circ \sequence {y_n} } + \NN$
Putting the operations on $\CC$ with those on $\CC \, \big / \NN$ gives:
:$+ :\quad \forall \sequence {x_n} + \NN, \sequence{y_n} + \NN \in \CC \, \big / \NN$:
:::$\quad \paren {\sequence {x_n} + \NN} + \paren {\sequence {y_n} + \NN} = \sequence {x_n + y_n} + \NN$
:$\circ :\quad \forall \sequence {x_n} + \NN, \sequence {y_n} + \NN \in \CC \, \big / \NN$: 
:::$\quad \paren {\sequence {x_n} + \NN} \paren {\sequence {y_n} + \NN} = \sequence {x_n y_n} + \NN$
{{qed}}
Category:P-adic Number Theory
jexmx3r1ybgzrr9tw4q827zig7m3exi
Theorem: Simple Graph of Maximum Size is Complete Graph

Let $G$ be a simple graph of order $n$ such that $n \ge 1$.
Let $G$ have the largest size of all simple graphs of order $n$.
Then:
:$G$ is the complete graph $K_n$
:its size is $\dfrac {n \paren {n - 1} } 2$.

Proof:
By definition, $K_n$ is the simple graph of order $n$ such that every vertex of $K_n$ is adjacent to all other vertices.
So, let $G$ have the largest size of all simple graphs of order $n$.
Then by definition of largest size, it is not possible for another edge to be added to $G$.
The only way that could be is if all the vertices of $G$ are already adjacent to all other vertices.
Hence $G = K_n$ by definition.
The size of $G$ then follows from Size of Complete Graph.
{{qed}}
Theorem: Simple Graph where All Vertices and All Edges are Adjacent

Let $G$ be a simple graph in which:
:every vertex is adjacent to every other vertex
and:
:every edge is adjacent to every other edge.
Then $G$ is of order no greater than $3$.

Proof:
It is seen that examples exist of simple graphs which fulfil the criteria where the order of $G$ is no greater than $3$:
:400px
The cases where the order of $G$ is $1$ or $2$ are trivial.
When the order of $G$ is $3$, the criteria can be verified by inspection.
Let the order of $G = \struct {V, E}$ be $4$ or more.
Let $v_1, v_2, v_3, v_4 \in V$.
Suppose every vertex is adjacent to every other vertex.
As $v_1$ is adjacent to $v_2$, there exists the edge $v_1 v_2$.
As $v_3$ is adjacent to $v_4$, there exists the edge $v_3 v_4$.
But $v_1 v_2$ and $v_3 v_4$ both join two distinct pairs of vertices.
Thus $v_1 v_2$ and $v_3 v_4$ are not adjacent, by definition.
So when there are $4$ or more vertices in $G$, it cannot fulfil the criteria.
{{qed}}
Theorem: Simple Graph whose Vertices all Incident but Edges not Adjacent

Let $G = \struct {V, E}$ be a simple graph such that:
:every vertex is incident with at least one edge
:no two edges are adjacent to each other.
Then $G$ has an even number of vertices.

Proof:
Suppose there exists a set of $3$ vertices that are connected.
Then at least one of these vertices has at least $2$ edges.
That would mean that at least $2$ edges were incident with the same vertex.
That is, that at least $2$ edges were adjacent to each other.
So, for a simple graph to fulfil the conditions, vertices can exist only in $2$-vertex components.
So such a simple graph must have an even number of vertices.
{{qed}}
Theorem: Size of Star Graph

Let $S_n$ denote the star graph of order $n$ where $n > 0$.
The size of $S_n$ is given by:
:$\size {S_n} = n - 1$

Proof:
By definition of star graph, one vertex is adjacent to all the $n - 1$ other vertices.
So the size of $S_n$ is at least $n - 1$.
All the other vertices are of degree $1$, and the edges they are incident with are the ones joining them to the distinguished vertex.
Those edges have already been counted.
So the size of $S_n$ is exactly $n - 1$.
{{qed}}
Category:Star Graphs
Category:Star Graphs
ot5nmixbbq2jsccss1d7ef75lpdn6gq
Theorem: Smallest Simple Graph with One Vertex Adjacent to All Others

Let $G = \struct {V, E}$ be a simple graph of order $n$.
Let $G$ be the simple graph with the smallest size such that one vertex is adjacent to all other vertices of $G$.
Then $G$ is the star graph of order $n$ and is of size $n - 1$.

Proof:
In order for the one vertex in question to be adjacent to all the others, it needs to be incident to $n - 1$ edges.
This is the smallest number of edges required.
Hence $G$ is a star graph.
From Size of Star Graph, the size of $G$ is thus $n - 1$.
{{qed}}
Theorem: Simple Graph whose Vertices Incident to All Edges

Let $G = \struct {V, E}$ be a simple graph whose vertices are incident to all its edges.
Then $G$ is either:
:the star graph $S_2$, which is also the complete graph $K_2$
:an edgeless graph of any order.

Proof:
If $G$ has no edges, then all the vertices are incident to all the edges vacuously.
So any of the edgeless graphs $N_n$ for order $n \in \Z_{\ge 0}$ fulfils the criterion.
Suppose $G$ has more than $2$ vertices $v_1, v_2, v_3$ and at least one edge.
{{WLOG}}, let one edge be $v_1 v_2$.
But $v_3$ cannot be incident to edge $v_1 v_2$.
So $G$ can have no more than $2$ vertices.
Furthermore, there can be only one edge joining those two vertices.
The result follows from inspection of $K_2$ and $S_2$.
{{qed}}
Theorem: Heine-Borel Theorem/Normed Vector Space

Let $\struct {X, \norm {\,\cdot\,} }$ be a finite-dimensional normed vector space.
A subset $K \subseteq X$ is compact {{iff}} $K$ is closed and bounded.

Proof:
=== Necessary Condition ===
{{:Heine-Borel Theorem/Normed Vector Space/Necessary Condition}}{{qed|lemma}}
Theorem: Characteristics of Cycle Graph

Let $G = \struct {V, E}$ be an (undirected) graph whose order is greater than $2$.
Then $G$ is a cycle graph {{iff}}:
:$G$ is connected
:every vertex of $G$ is adjacent to $2$ other vertices
:every edge of $G$ is adjacent to $2$ other edges.

Proof:
Recall that a cycle is a closed walk with the properties:
:all its edges are distinct
:all its vertices (except for the start and end) are distinct.
From Cycle Graph is Connected, $G$ is connected.
From Cycle Graph is 2-Regular, $G$ is $2$-regular.
Hence every vertex of $G$ is incident with $2$ edges.
{{finish|I hate trying to prove obvious things}}
Theorem: Maximum Number of Arcs in Digraph

Let $D_n$ be a digraph of order $n$ such that $n \ge 1$.
Let $D_n$ have the greatest number of arcs of all digraphs of order $n$.
The number of arcs in $D$ is given by:
:$\size {D_n} = n \paren {n - 1}$

Proof:
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\size {D_n} = n \paren {n - 1}$
Theorem: P-adic Norm of p-adic Number is Power of p/Lemma

Let $\norm {\,\cdot\,}_p$ be the $p$-adic norm on the rationals $\Q$ for some prime $p$.
Let $\sequence {x_n}$ be a Cauchy sequence in $\struct{\Q, \norm {\,\cdot\,}_p}$ such that $\sequence {x_n}$ does not converge to $0$.
Then:
:$\exists v \in \Z: \ds \lim_{n \mathop \to \infty} \norm{x_n}_p = p^{-v}$

Proof:
From P-adic Norm on Rational Numbers is Non-Archimedean Norm, $p$-adic norm is a non-Archimedean norm on the rationals $\Q$.
Since $\sequence {x_n}$ does not converge to $0$, from Non-Null Cauchy Sequence in Non-Archimedean Norm is Eventually Stationary:
:$\exists N \in \N: \forall n, m > N: \norm {x_n}_p = \norm {x_m}_p$
By definition of the $p$-adic norm on $\Q$:
:$\exists v \in \Z: \norm {x_{N + 1} }_p = p^{-v}$
Therefore:
:$\forall n > N: \norm {x_n}_p = \norm {x_{N + 1} }_p = p^{-v}$
Let $\sequence {y_n}$ be the subsequence of $\sequence {\norm {x_n}}$ defined by:
:$\forall n: y_n = \norm {x_{N + n} }_p$
Then $\sequence {y_n}$ is the constant sequence $\tuple {p^{-v}, p^{-v}, p^{-v}, \dotsc}$.
Therefore:
{{begin-eqn}}
{{eqn | l = \lim_{n \mathop \to \infty} \norm {x_n}_p
      | r = \lim_{n \mathop \to \infty} y_n
      | c = Limit of Subsequence equals Limit of Real Sequence
}}
{{eqn | r = p^{-v}
      | c = Constant Sequence Converges to Constant in Normed Division Ring
}}
{{end-eqn}}
{{qed}}
Category:P-adic Norm of p-adic Number is Power of p
fyhi08816ok458kmp7kf58mp4m44lu0
Theorem: Loop-Digraph as a Relation

A loop-digraph is the same thing as a relational structure.

Proof:
A loop-digraph is a graph such that:
:it is not necessarily antireflexive
:it is not necessarily symmetric.
Hence a loop-digraph is an ordered pair:
:$G = \struct {V, E}$
such that:
:$V$ is a set of objects
:$E$ is a relation on $V$.
This defines a relational structure.
{{qed}}
Theorem: Complete Graph is Hamiltonian for Order Greater than 2

Let $n \in \Z$ be an integer such that $n > 2$.
Let $K_n$ denote the complete graph of order $n$.
Then $K_n$ is Hamiltonian.

Proof:
First we note that when $n = 2$ there is one edge in $K_n$.
So if you start at one vertex $u$ and travel along that edge to the other vertex $v$, you cannot return to $u$ except by using that same edge.
Consequently $K_2$ is not Hamiltonian.
{{qed|lemma}}
Let $n = 4$.
Let us take two vertices $u, v$ of $K_n$:
From Complete Graph is Regular, the degrees of $u$ and $v$ are given by:
:$\map \deg u = \map \deg v = n - 1$
Let us remove the edge $u v$ which joins them.
Let the resulting graph be denoted $G$.
We now have that:
:$\map \deg u = \map \deg v = n - 2$
From Ore's Theorem, $G$ is Hamiltonian if for each pair of non-adjacent vertices $u, v \in V$:
:$\deg u + \deg v \ge n$
In $G$, we have that:
Hence:
{{begin-eqn}}
{{eqn | l = \deg u + \deg v
      | r = 2 \paren {n - 2}
      | c = 
}}
{{eqn | r = n + \paren {n - 4}
      | c = 
}}
{{eqn | o = \ge
      | r = n
      | c = as $n \ge 4$
}}
{{end-eqn}}
Thus $G$ is Hamiltonian.
A Hamiltonian graph with another edge added is still Hamiltonian.
Thus restoring the edge $u v$ to $G$ to turn it back into $K_n$ means that $K_n$ is Hamiltonian.
{{qed|lemma}}
When $n = 3$ we cannot use this theorem, as you then find for the resulting $G$:
:$\deg u + \deg v = 2$
which is less than $3$.
Instead we inspect the complete graph $K_3$ and see it is is the cycle graph $C_3$
:200px
The result follows from Cycle Graph is Hamiltonian.
{{qed}}
Category:Complete Graphs
Category:Hamiltonian Graphs
cqxn2bajtfwoms7u8vcqv9cvu9gkvym
Theorem: Cycle Graph is Hamiltonian

Let $n \in \Z$ be an integer such that $n \ge 3$.
Let $C_n$ denote the cycle graph of order $n$.
Then $C_n$ is Hamiltonian.

Proof:
Recall the definition of a Hamiltonian graph:
:$G$ is Hamiltonian {{iff}} it is an undirected graph that contains a cycle that contains every vertex of $G$ (but not necessarily every edge of $G$).
A cycle graph is a graph which consists of a single cycle.
So all the vertices of $C_n$ are on the same cycle.
The result follows.
{{Qed}}
Category:Cycle Graphs
Category:Hamiltonian Graphs
8cd9mels644ewnch816ytybnd3liulj
Theorem: Maximum Degree of Vertex in Simple Graph

Let $G = \struct {V, E}$ be a simple graph.
Let $\card V$ denote the order of $G$.
Then no vertex of $G$ has a degree higher than $\card V - 1$.

Proof:
By definition, a simple graph has no loops or multiple edges.
So a vertex can be incident to only as many edges that will join it to all the other vertices once each.
There are $\card V - 1$ other vertices.
Hence the result.
{{qed}}
Theorem: Degrees of Vertices determine Order and Size of Graph

Let $G = \struct {V, E}$ be a simple graph.
Let the degrees of each of the vertices of $G$ be given.
Then it is possible to determine both the order $\card V$ and size $\card E$ of $G$.

Proof:
Suppose we are given the degrees of each of the vertices of $G$.
By definition, $\card V$ is simply the count of the vertices.
So if we have been given the degrees of each of the vertices, we must know how many vertices there are.
Then from the Handshake Lemma:
:$\ds \sum_{v \mathop \in V} \map \deg v = 2 \card E$
That is, the sum of the degrees of all the vertices is equal to twice $\card E$.
So to find the size of $G$, add up the degrees of all the vertices and divide by $2$.
{{qed}}