avewright/proofwiki-math huggingface dataset:
Theorem: Inverse of Composite Bijection/Proof 2

Let $f$ and $g$ be bijections.
Then:
:$\paren {g \circ f}^{-1} = f^{-1} \circ g^{-1}$
and $f^{-1} \circ g^{-1}$ is itself a bijection.

Proof:
Let $f: X \to Y$ and $g: Y \to Z$ be bijections.
Then:
{{begin-eqn}}
{{eqn | l = \paren {g \circ f} \circ \paren {f^{-1} \circ g^{-1} }
      | r = g \circ \paren {\paren {f \circ f^{-1} } \circ g^{-1} }
      | c = Composition of Mappings is Associative
}}
{{eqn | r = g \circ \paren {I_Y \circ g^{-1} }
      | c = Composite of Bijection with Inverse is Identity Mapping
}}
{{eqn | r = g \circ g^{-1}
      | c = Identity Mapping is Left Identity
}}
{{eqn | r = I_Z
      | c = Composite of Bijection with Inverse is Identity Mapping
}}
{{end-eqn}}
{{qed|lemma}}
{{begin-eqn}}
{{eqn | l = \paren {f^{-1} \circ g^{-1} } \circ \paren {g \circ f}
      | r = \paren {f^{-1} \circ \paren {g^{-1} \circ g} } \circ f
      | c = Composition of Mappings is Associative
}}
{{eqn | r = \paren {f^{-1} \circ I_Y} \circ f
      | c = Composite of Bijection with Inverse is Identity Mapping
}}
{{eqn | r = f^{-1} \circ f
      | c = Identity Mapping is Right Identity
}}
{{eqn | r = I_X
      | c = Composite of Bijection with Inverse is Identity Mapping
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Equivalence of Definitions of Set Partition

Let $S$ be a set
{{TFAE|def = Set Partition}}

Proof:
=== Definition 1 implies Definition 2 ===
Let $\Bbb S$ be a set of subsets $\Bbb S$ of $S$ such that:
:$(1): \quad$ $\Bbb S$ is pairwise disjoint: $\forall S_1, S_2 \in \Bbb S: S_1 \cap S_2 = \O$ when $S_1 \ne S_2$
:$(2): \quad$ The union of $\Bbb S$ forms the whole set $S$: $\ds \bigcup \Bbb S = S$
:$(3): \quad$ None of the elements of $\Bbb S$ is empty: $\forall T \in \Bbb S: T \ne \O$.
By $(3)$ all sets in $\Bbb S$ are non-empty.
{{AimForCont}} there exists $x \in S$ in more than one set of $\Bbb S$.
That is:
:$\exists S_1, S_2 \in \Bbb S, S_1 \ne S_2: x \in S_1 \land x \in S_2$
Then by definition of set intersection:
:$x \in S_1 \cap S_2$
and so $S_1 \cap S_2 \ne \O$.
This contradicts condition $(1)$.
So no element of $S$ can be in more than one set of $\Bbb S$.
{{AimForCont}} there exists $x \in S$ in none of the sets of $\Bbb S$.
Then $\ds x \notin \bigcup \Bbb S$ and so $\Bbb S \notin S$.
This contradicts condition $(2)$.
So every element of $S$ is in at least one set of $\Bbb S$.
Thus $x$ lies in exactly one element of $\Bbb S$.
Hence it follows that $\Bbb S$ is a set of non-empty subsets of $S$ such that each element of $S$ lies in exactly one element of $\Bbb S$.
{{qed|lemma}}
Theorem: Sierpiński's Theorem

Let $\struct {S, \tau}$ be a compact connected Hausdorff space.
Let $\set {F_n: n \in \N}$ be a pairwise disjoint closed cover of $S$.
Then $F_n = S$ for some $n \in \N$.

Proof:
{{ProofWanted}}
{{Namedfor|Wacław Franciszek Sierpiński|cat = Sierpiński}}
Category:Sierpiński's Theorem
Category:Compact Topological Spaces
Category:Connected Topological Spaces
Category:Hausdorff Spaces
3kz794mirt45g3uftjah3hiam1yrdsn
Theorem: Sierpiński's Theorem/Lemma 1

Let $\struct {S, \tau}$ be a compact connected Hausdorff space.
Let $A$ be a closed, non-empty proper subset of $S$.
Let $C$ be a component of $A$.
Then:
:$C \cap \partial A \ne \O$
where $\partial A$ denotes the boundary of $A$.

Proof:
Let $p \in C$.
Let $\VV$ be the set of all subsets of $A$ containing $p$ that are clopen relative to $A$..
By Quasicomponents and Components are Equal in Compact Hausdorff Space and Quasicomponent is Intersection of Clopen Sets:
:$C$ is the intersection of $\VV$.
{{AimForCont}}:
:$C \cap \partial A = \O$
By Boundary of Set is Closed, $K \cap \partial A$ is closed for each $K \in \VV$.
Thus by Compact Space satisfies Finite Intersection Axiom, there exists a finite set $\VV' \subseteq \VV$ such that $\partial A \cap \bigcap \VV' = \O$.
But then:
:$\ds K = \bigcap \VV' \in \VV$
{{explain|Where from?}}
Therefore there exists a $K \in \VV$ such that $K \cap \partial A = \O$.
Since $A$ is closed in $S$, and $K$ is clopen in $A$, $K$ is closed in $S$.
{{explain|Where from?}}
We have that:
:$\partial A = A^- \setminus \map {\operatorname {Int} } A$
where $A^-$ is the closure of $A$ and $\map {\operatorname {Int} } A$ is the interior of $A$
{{explain|Where from?}}
Hence as $K \subseteq A$, it follows that $K \subseteq \map {\operatorname {Int} } A$.
Since $K$ is open relative to $A$, it is open relative to $\map {\operatorname {Int} } A$.
{{explain|"open relative"}}
{{explain|Where from?}}
We have that $\map {\operatorname {Int} } A$ is open in $S$.
{{explain|Where from?}}
Therefore $K$ is open in $S$.
Thus $K$ is clopen in $S$.
We have that $p \in K \subseteq A \subsetneqq S$.
{{explain|Where from?}}
Therefore $S$ is not connected.
{{explain|Where from?}}
From this contradiction it follows that:
:$C \cap \partial A \ne \O$
{{qed}}
Category:Sierpiński's Theorem
awzv3b8vsx415573lhuedjp5jsqoas6
Theorem: Quasicomponent of Compact Hausdorff Space is Connected

Let $\struct {X, \tau}$ be a compact Hausdorff space.
Let $C$ be a quasicomponent of $\struct {X, \tau}$.
Then $C$ is connected.

Proof:
Let $p \in C$.
{{AimForCont}} $C$ is not connected.
Therefore, by definition of connected, there exist disjoint closed sets $A, B$ of $\struct {X, \tau}$ such that $C = A \cup B$.
By Compact Hausdorff Space is $T_4$, there exist disjoint open sets $U, V$ of $\struct {X, \tau}$ such that $U \supseteq A$ and $V \supseteq B$.
By Quasicomponent is Intersection of Clopen Sets, $C$ is the intersection of all clopen sets of $\struct {X, \tau}$ containing $p$.
Since $U$ and $V$ are open, $X \setminus \paren {U \cup V}$ is closed.
Hence $X \setminus \paren {U \cup V}$ is compact.
{{explain|Where from?}}
Let $S$ be the set of clopen sets of $\struct {X, \tau}$ containing $p$.
Let $S'$ be the set of complements relative to $\struct {X, \tau}$ of elements of $S$.
Then $S'$ is an open cover of $X \setminus \paren {U \cup V}$.
{{explain|Needs explaining as to why - might be worth elaborating the fact that $X \setminus \paren {U \cup V} \subseteq X \setminus C$ in order for the above to hold.}}
Thus by compactness has a finite subcover $T'$.
{{explain|specifically, what has, and why - compactness of what? Above sentence is incomplete.}}
Let $T$ be the set of complements of elements of $T'$.
{{explain|complements relative to what?}}
Then $\ds C \subseteq \bigcap T \subseteq U \cup V$.
{{explain|why?}}
Furthermore, since $T$ is a finite set of clopen sets of $\struct {X, \tau}$]], $\bigcap T$ is clopen.
Let $\ds U' = U \cap \bigcap T$ and let $\ds V' = V \cap \bigcap T$.
Then $C \subseteq U' \cup V' = T$.
{{explain|Where from?}}
Since $T$ is clopen, so is $U'$.
But $C$ contains points in $U'$ and points not in $U'$, contradicting the fact that $C$ is a quasicomponent of $\struct {X, \tau}$.
{{explain|What specifically is the nature of the relation between $U'$ and $C$ which invalidates one or more criteria for $C$ to be a quasicomponent?}}
It follows that $C$ is connected.
{{qed}}
Category:Compact Topological Spaces
Category:Connectedness Between Two Points
dt7xapr6pk3fdclqgahvowthq3t17z4
Theorem: Quasicomponents and Components are Equal in Compact Hausdorff Space

Let $T = \struct {S, \tau}$ be a compact Hausdorff space.
Then for each $A \subseteq S$:
$A$ is a component of $S$ {{iff}} $A$ is a quasicomponent of $S$.

Proof:
{{ProofWanted|Follows from Quasicomponent of Compact Hausdorff Space is Connected}}
Category:Components (Topology)
Category:Quasicomponents
Category:Hausdorff Spaces
Category:Compact Topological Spaces
cos06oigo8cvp9miduovwh82etykfqa
Theorem: Derived Set in T1 Space is Closed

Let $\struct {X, \tau}$ be a $T_1$ space.
Let $S \subseteq X$.
Let $S'$ be the derived set of $S$.
Then $S'$ is closed.

Proof:
Let $x \in S' '$.
Let $U$ be an open neighborhood of $x$.
Then by the definition of derived set, $U$ contains an element $y$ of $S'$ such that $x \ne y$.
Then $U \setminus \set x$ is an open neighborhood of $y$ by the definition of a $T_1$ space.
The definition of derived set is applied once more to see that $U \setminus \set x$ contains an element $z$ of $S$.
Thus $z \in U \cap S$ and $z \ne x$.
As this holds for all open neighborhoods $U$ of $x$, it follows that $x \in S'$.
This holds for all $x \in S' '$.
It follows by definition of subset that $S' ' \subseteq S'$.
Thus $S'$ is closed.
{{qed}}
Category:Topology
7p5441u6beczj8lvs490ehe1ipt0ydt
Theorem: Equivalence of Axiom Schemata for Groups/Warning

Suppose we build an algebraic structure with the following axioms:
{{begin-axiom}}
{{axiom | n = 0
        | lc= Closure Axiom
        | q = \forall a, b \in G
        | ml= a \circ b
        | mo= \in
        | mr= G
}}
{{axiom | n = 1
        | lc= Associativity Axiom
        | q = \forall a, b, c \in G
        | ml= a \circ \paren {b \circ c}
        | mo= =
        | mr= \paren {a \circ b} \circ c
}}
{{axiom | n = 2
        | lc= Right Identity Axiom
        | qq= \exists e \in G
        | q = \forall a \in G
        | ml= a \circ e
        | mo= =
        | mr= a
}}
{{axiom | n = 3
        | lc= Left Inverse Axiom
        | qq= \forall x \in G
        | q = \exists b \in G
        | ml= b \circ a
        | mo= =
        | mr= e
}}
{{end-axiom}}
Then this does '''not''' (necessarily) define a group (although clearly a group fulfils those axioms).

Proof:
Let $\struct {S, \circ}$ be the algebraic structure defined as:
:$\forall x, y \in S: x \circ y = x$
That is, $\circ$ is the left operation.
From Element under Left Operation is Right Identity, every element serves as a right identity.
Then given any $a \in S$, we have that:
:$x \circ a = x$
As $x$ is an identity, axiom $(3)$ is also fulfilled.
But from More than one Right Identity then no Left Identity, there is no left identity and therefore no identity element.
Hence $\struct {S, \circ}$ is not a group.
{{qed}}
Theorem: Multiplicative Inverse in Monoid of Integers Modulo m

Let $\struct {\Z_m, \times_m}$ be the multiplicative monoid of integers modulo $m$.
Then:
:$\eqclass k m \in \Z_m$ has an inverse in $\struct {\Z_m, \times_m}$
{{iff}}:
:$k \perp m$

Proof:
First, suppose $k \perp m$.
That is:
:$\gcd \set {k, m} = 1$
By Bézout's Identity:
:$\exists u, v \in \Z: u k + v m = 1$
Thus:
:$\eqclass {u k + v m} m = \eqclass {u k} m = \eqclass u m \eqclass k m = \eqclass 1 m$
Thus:
:$\eqclass u m$ is an inverse of $\eqclass k m$
Suppose that:
:$\exists u \in \Z: \eqclass u m \eqclass k m = \eqclass {u k} m = 1$
Then:
:$u k \equiv 1 \pmod m$
and:
:$\exists v \in \Z: u k + v m = 1$
Thus from Bézout's Identity, $k \perp m$.
{{qed}}
Theorem: Element Commutes with Square in Group

Let $\left({G, \circ}\right)$ be a group.
Let $x \in G$.
Then $x$ commutes with $x \circ x$.

Proof:
{{begin-eqn}}
{{eqn | l = x \circ \paren {x \circ x}
      | r = \paren {x \circ x} \circ x
      | c = {{Group-axiom|1}}
}}
{{end-eqn}}
{{qed}}
Theorem: Element Commutes with Square in Group

Let $\left({G, \circ}\right)$ be a group.
Let $x \in G$.
Then $x$ commutes with $x \circ x$.

Proof:
By definition, a group is also a semigroup.
Thus the result Element Commutes with Square in Semigroup can be applied.
{{qed}}
Theorem: Element Commutes with Square in Semigroup

Let $\struct {S, \circ}$ be a semigroup.
Let $x \in S$.
Then $x$ commutes with $x \circ x$.

Proof:
{{Semigroup-axiom|0}} is taken for granted.
{{begin-eqn}}
{{eqn | q = \forall x \in S
      | l = x \circ \paren {x \circ x}
      | r = \paren {x \circ x}\circ x
      | c = {{Semigroup-axiom|1}}
}}
{{end-eqn}}
{{qed}}
Category:Semigroups
f4pvi4mb2pc2hp7dhf8j8zjwdrqo6wu
Theorem: Sufficient Condition for Vector Equals Inverse iff Zero

Let $\struct {\mathbf V, +, \circ}_\GF$ be a vector space over a field $\GF$, as defined by the vector space axioms.
Let $\GF$ be infinite.
Then:
:$\forall \mathbf v, -\mathbf v \in \mathbf V: \mathbf v = - \mathbf v \iff \mathbf v = \mathbf 0$

Proof:
=== Necessary Condition ===
{{begin-eqn}}
{{eqn | l = \mathbf v
      | r = \mathbf 0
      | c = {{hypothesis}}
}}
{{eqn | ll= \leadsto
      | l = -1_\GF \circ \mathbf v
      | r = -1_\GF \circ \mathbf 0
      | c = scaling both sides by the negative of the unity of $\GF$
}}
{{eqn | ll= \leadsto
      | l = -\mathbf v
      | r = \mathbf 0
      | c = Vector Inverse is Negative Vector, Zero Vector Scaled is Zero Vector
}}
{{eqn | ll= \leadsto
      | l = \mathbf v
      | r = -\mathbf v
}}
{{end-eqn}}
{{qed|lemma}}
Theorem: Subsets of Disjoint Sets are Disjoint

Let $S$ and $T$ be disjoint sets.
Let $S' \subseteq S$ and $T' \subseteq T$.
Then $S'$ and $T'$ are disjoint.

Proof:
Let $S \cap T = \O$.
Let $S' \subseteq S$ and $T' \subseteq T$.
{{AimForCont}} $S' \cap T' \ne \O$.
Then:
{{begin-eqn}}
{{eqn | l = \exists x
      | o = \in
      | r = S' \cap T'
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x 
      | o = \in
      | r = S'
      | c = {{Defof|Set Intersection}}
}}
{{eqn | lo= \land
      | l = x 
      | o = \in
      | r = T'
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x 
      | o = \in
      | r = S
      | c = {{Defof|Subset}}
}}
{{eqn | lo= \land
      | l = x 
      | o = \in
      | r = T
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x 
      | o = \in
      | r = S \cap T
      | c = {{Defof|Set Intersection}}
}}
{{eqn | ll= \leadsto
      | l = S \cap T
      | o = \ne
      | r = \O
      | c = {{Defof|Set Intersection}}
}}
{{end-eqn}}
From this contradiction:
:$S' \cap T' = \O$
Hence the result by definition of disjoint sets.
{{qed}}
Theorem: Network with Positive Integer Mapping is Multigraph

Let $N = \struct {V, E, w}$ be a network whose weights are all strictly positive integers.
Then $N$ can be represented as a multigraph.
Conversely, any multigraph can be expressed as a network whose weights are all strictly positive integers.

Proof:
=== Network as Multigraph ===
Let $N = \struct {V, E, w}$ be a network, either directed or undirected.
{{WLOG}}, suppose $N$ is undirected, and in the following argument allow the term edge to include arcs.
Let $e \in E$ be an edge of the underlying graph $\struct {V, E}$ of $N$.
Let $e = u v$, where $u, v \in V$ are vertices of the underlying graph $\struct {V, E}$ of $N$.
Let $n = \map w e$ be the weight of $e$.
By hypothesis, $n$ is a strictly positive integer.
Let $n$ edges be identified between $u$ and $v$.
Repeat this process for all edges of $N$.
The resulting object is a multigraph.
Theorem: Complete Graph is Regular

Let $K_p$ be the complete graph of order $p$.
Then $K_p$ is $p-1$-regular.

Proof:
By definition of complete graph, $K_p$ has $p$ vertices.
Also by definition of complete graph, each vertex of $K_p$ is adjacent to all the other $p - 1$ vertices of $K_p$.
As $K_p$ is a simple graph, there can be only one edge joining any pair of vertices of $K_p$.
So each vertex of $K_p$ has $p - 1$ edges to which it is incident.
So, by definition, $K_p$ is $p-1$-regular.
{{qed}}
Theorem: No Simple Graph is Perfect

Let $G$ be a simple graph whose order is $2$ or greater.
Then $G$ is not perfect.

Proof:
Recall that a perfect graph is one where each vertex is of different degree.
We note in passing that the simple graph consisting of one vertex trivially fulfils the condition for perfection.
{{AimForCont}} $G$ is a simple graph of order $n$ where $n \ge 2$ such that $G$ is perfect.
First, suppose that $G$ has no isolated vertices.
By the Pigeonhole Principle, for all vertices to have different degrees, one of them must be of degree at least $n$.
That means it must connect to at least $n$ other vertices.
But there are only $n - 1$ other vertices to connect to.
Therefore $G$ cannot be perfect.
Now suppose $G$ has an isolated vertex.
There can be only one, otherwise there would be two vertices of degree zero, and so $G$ would not be perfect.
Again by the Pigeonhole Principle, for all vertices to have different degrees, one of them must be of degree at least $n - 1$.
But of the remaining $n - 1$ vertices, one of them is of degree zero.
So it cannot be adjacent to any vertex.
So there are only $n - 2$ other vertices to connect to.
Therefore $G$ cannot be perfect.
{{qed}}
Theorem: Continuum Property implies Well-Ordering Principle

The Continuum Property of the positive real numbers $\R_{\ge 0}$ implies the Well-Ordering Principle of the natural numbers $\N$.

Proof:
Suppose that the set of positive real numbers $\R_{\ge 0}$ has the Continuum Property.
{{AimForCont}} $T \subseteq \N$ is a subset of $\N$ which has no smallest element.
Then:
:$\forall t \in T: \exists u \in T: u < t$
Let $A \in \R_{\ge 0}$.
For every $t \in T$, let $a_t = \dfrac A {2^t}$.
We have that $t \in \N$, so $t \ge 0$.
Therefore $2^t \ge 1$.
This $a_t$ can never be greater than $A$.
Therefore $\set {a_t: t \in T}$ has an upper bound.
As $\R_{\ge 0}$ has the Continuum Property, it follows that $\set {a_t: t \in T}$ has a supremum $B$.
We have that $\dfrac {7 B} 8 < B$.
Thus $\dfrac {7 B} 8$ is not an upper bound of $\set {a_t: t \in T}$.
Therefore there exists $m \in T$ such that:
:$a_m > \dfrac {7 B} 8$
Then there is $n \in T$ such that $n < m$. 
Let $n = m - p$. 
Then:
{{begin-eqn}}
{{eqn | l = a_n
      | r = \dfrac A {2^n}
}}
{{eqn | r = \dfrac A {2^{m - p} }
}}
{{eqn | r = \dfrac {A \cdot 2^p} {2^m}
}}
{{eqn | o = \ge
      | r = \dfrac {A \cdot 2} {2^m}
}}
{{eqn | r = 2 \cdot a_m
}}
{{eqn | o = >
      | r = 2 \cdot \dfrac {7B} 8
}}
{{eqn | r = \dfrac {7B} 4
}}
{{eqn | o = >
      | r = B
}}
{{end-eqn}}
Therefore $a_n > B$.
This contradicts the supposition that $B$ is the supremum of $\set {a_t: t \in T}$
Thus our initial supposition that $T \subseteq \N$ has no smallest element was false.
As $T$ is arbitrary, it follows that each $T \subseteq \N$ has a smallest element.
Thus the Well-Ordering Principle holds for $\N$, as was to be proved.
{{qed}}
Theorem: Circuit of Simple Graph has Three Edges or More

Let $G$ be a simple graph.
Let $C$ be a circuit in $G$.
Then $C$ has at least $3$ edges.

Proof:
By definition, a circuit contains at least one edge.
That is, a single vertex does not comprise a trivial degenerate circuit with no edges.
Suppose $C$ contains only one edge $e$.
As $G$ is a simple graph it contains no loops.
Therefore $e$ starts and ends at two distinct vertices.
Therefore $C$, consisting entirely of $e$ can not be a circuit.
Suppose $C$ contains exactly $2$ edges $e$ and $f$.
Let $e = u v$ where $u$ and $v$ are vertices of $G$.
Then for $C$ to be a circuit it must follow that $f = v u$.
Thus there are two edges between the same vertices $v$ and $u$.
As $G$ is an undirected graph, it must be that $e$ and $f$ are part of a multiple edge between $u$ and $v$.
But $G$ is not a multigraph, and so such a circuit can not exist.
A circuit containing $3$ edges definitely exists, though.
Let $G = \struct {V, E}$ where $V = \set {u, v, w}$ and $E = \set {\set {u, v}, \set {u, w}, \set {v, w} }$.
Then $\tuple {u, w, v, u}$ is a $3$-edge circuit.
{{qed}}
Theorem: Cut-Vertex divides Graph into Two or More Components

Let $G$ be a graph.
Let $v$ be a cut-vertex of $G$.
Then the vertex deletion $G - v$ contains $2$ or more components.

Proof:
By definition of cut-vertex, $G - v$ contains at least $2$ components.
That it can contain more components than $2$ is best proved by illustration:
:520px
{{qed}}
Theorem: Bridge divides Graph into Two Components

Let $G$ be a connected graph.
Let $e$ be a bridge of $G$.
Then the edge deletion $G - e$ contains exactly $2$ components.

Proof:
Let $G$ be a connected graph and $e = u v$ be a bridge of $G$.
By definition of bridge, $G - e$ has to be of at least $2$ components.
{{AimForCont}} $G - e$ were of more than $2$ components.
Let $G_1, G_2, G_3$ be $3$ of those components such that $u \in G_1$ and $v \in G_2$.
Note that $u$ and $v$ cannot both be in the same component or $e$ would not be a bridge.
Now let $e$ be replaced so as to connect $G_1$ and $G_2$ again.
Then $G_3$ would still be disconnected from the rest of $G$, and $G$ itself would therefore be a disconnected graph.
From this contradiction it follows that $G - e$ can only be of two components.
{{qed}}
Theorem: Connected Graph with only Even Vertices has no Bridge

Let $G$ be a connected graph whose vertices are all even.
Then no edge of $G$ is a bridge.

Proof:
Let the vertices of $G$ all be even.
Then by Characteristics of Eulerian Graph, $G$ is Eulerian.
By definition of Eulerian, $G$ therefore contains a Eulerian circuit.
Thus every edge of $G$ lies on a circuit of $G$.
From Condition for Edge to be Bridge, if an edge $e$ of $G$ is a bridge, then it does not lie on a circuit.
Hence no edge of $G$ is a bridge.
{{qed}}
Theorem: Graph of Cube is Hamiltonian

The graph of the cube is Hamiltonian.

Proof:
Proof by demonstration:
:400px
A Hamiltonian cycle is indicated in {{color|blue}}.
{{qed}}
Theorem: Graph of Icosahedron is Hamiltonian

The graph of the icosahedron is Hamiltonian.

Proof:
Proof by demonstration:
:400px
A Hamiltonian cycle is indicated in <span style="color:blue">blue</span>.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition

Let $T$ be a tree of order $n$.
Then the size of $T$ is $n-1$.

Proof:
Suppose $T$ is a tree with $n$ nodes. We need to show that $T$ has $n - 1$ edges.
The proof proceeds by strong induction.
Let $T_n$ be a tree with $n$ nodes.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition that a tree with $n$ nodes has $n - 1$ edges.
=== Basis for the Induction ===
$\map P 1$ says that a tree with $1$ node has no edges.
It is clear that $T_1$ is $N_1$, the edgeless graph, which has $1$ node and no edges.
So $\map P 1$ is (trivially) true.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P j$ is true for all $1 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:Every tree with $j$ nodes such that $1 \le j \le k$ has $j - 1$ edges.
Then we need to show:
:Every tree with $k + 1$ nodes has $k$ edges.
=== Induction Step ===
{{:Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition/Induction Step}}
==== Induction Step: Proof 1 ====
{{:Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition/Induction Step/Proof 1}}
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
{{qed|lemma}}
==== Induction Step: Proof 2 ====
{{:Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition/Induction Step/Proof 2}}
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition

Let $T$ be a tree of order $n$.
Then the size of $T$ is $n-1$.

Proof:
Let $T_{k + 1}$ be an arbitrary tree with $k + 1$ nodes.
Take any node $v$ of $T_{k + 1}$ of degree $1$.
Such a node exists from Finite Tree has Leaf Nodes.
Consider $T_k$, the subgraph of $T_{k + 1}$ created by removing $v$ and the edge connecting it to the rest of the tree.
By Connected Subgraph of Tree is Tree, $T_k$ is itself a tree.
The order of $T_k$ is $k$, and it has one less edge than $T_{k + 1}$ by definition.
We have {{hypothesis}} that $T_k$ has $k - 1$ edges.
So $T_{k + 1}$ must have $k$ edges.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order/Necessary Condition

Let $T$ be a tree of order $n$.
Then the size of $T$ is $n-1$.

Proof:
Let $T_{k + 1}$ be an arbitrary tree with $k + 1$ nodes.
Remove any edge $e$ of $T_{k + 1}$.
By definition of tree $T_{k + 1}$ has no circuits.
Therefore from Condition for Edge to be Bridge it follows that $e$ must be a bridge.
So removing $e$ disconnects $T_{k + 1}$ into two trees $T_1$ and $T_2$, with $k_1$ and $k_2$ nodes, where $k_1 + k_2 = k + 1$.
Then, {{hypothesis}}, $T_1$ and $T_2$ have $k_1 - 1$ and $k_2 - 1$ edges.
Putting the edge $e$ back again, it can be seen that $T_{k + 1}$ has $\paren {k_1 - 1} + \paren {k_2 - 1} + 1 = k$ edges.
Therefore a tree of order $k + 1$  is of size $k$.