nyuuzyou/wikis huggingface dataset:
Conjugates of Elements in Centralizer

== Theorem ==
Let $G$ be a group.
Let $\map {C_G} a$ be the centralizer of $a$ in $G$.
Then $\forall g, h \in G: g a g^{-1} = h a h^{-1}$ $g$ and $h$ belong to the same left coset of $\map {C_G} a$.
== Proof ==
The centralizer of $a$ in $G$ is defined as:
:$\map {C_G} a = \set {x \in G: x \circ a = a \circ x}$
Let $g, h \in G$.
Then:
By Elements in Same Left Coset iff Product with Inverse in Subgroup:
:$g$ and $h$ belong to the same left coset of $\map {C_G} a$ $g^{-1} h \in \map {C_G} a$.
The result follows.
== Sources ==
* : $\S 42$. Another approach to cosets: Worked Example $2$
Category:Conjugacy
Category:Centralizers
Category:Cosets
Conjugates of Transpositions

== Theorem ==
Let $k_1, k_2, k_3 \in \left\{{1, 2, \ldots, n}\right\}$.
Then:
: $(1): \quad \begin{bmatrix} k_1 & k_2 \end{bmatrix} = \begin{bmatrix} k_3 & k_2 \end{bmatrix} \begin{bmatrix} k_1 & k_3 \end{bmatrix} \begin{bmatrix} k_3 & k_2 \end{bmatrix}$
: $(2): \quad \begin{bmatrix} k_1 & k_2 \end{bmatrix} = \begin{bmatrix} k_3 & k_1 \end{bmatrix} \begin{bmatrix} k_3 & k_2 \end{bmatrix} \begin{bmatrix} k_3 & k_1 \end{bmatrix}$
== Proof ==
$(1):$ Calculating the product of $\begin{bmatrix} k_3 & k_2 \end{bmatrix} \begin{bmatrix} k_1 & k_3 \end{bmatrix} \begin{bmatrix} k_3 & k_2 \end{bmatrix}$:
:: $k_1 \to k_3 \to k_2$
:: $k_2 \to k_3 \to k_1$
:: $k_3 \to k_2 \to k_3$
hence the result.
$(2):$ Calculating the product of $\begin{bmatrix} k_3 & k_1 \end{bmatrix} \begin{bmatrix} k_3 & k_2 \end{bmatrix} \begin{bmatrix} k_3 & k_1 \end{bmatrix}$:
:: $k_1 \to k_3 \to k_2$
:: $k_2 \to k_3 \to k_1$
:: $k_3 \to k_1 \to k_3$
hence the result.
Category:Symmetric Groups
Conjugation in C*-Algebra preserves Positivity

== Theorem ==
Let $\struct {A, \ast, \norm {\, \cdot \,} }$ be a $\text C^\ast$-algebra.
Let $a \in A$ be positive.
Let $c \in A$.
Then $c^\ast a c$ is positive.
=== Corollary ===
== Proof ==
Since $a$ is positive, there exists a positive $b \in A$ such that $a = b^2$ from Existence and Uniqueness of Positive Nth Root of Positive Element of C*-Algebra.
We then have:
:$\paren {b c}^\ast \paren {b c} = c^\ast b^2 c = c^\ast a c$
From Product of Element of C*-Algebra with its Star is Positive, we have that $\paren {b c}^\ast \paren {b c}$ is positive.
Hence $c^\ast a c$ is positive.
== Sources ==
* : $2.2$: Positive Elements of $C^\ast$-Algebras
Category:Positive Elements of C*-Algebras
Category:Conjugation in C*-Algebra preserves Positivity
Conjugation in C*-Algebra preserves Positivity/Corollary

== Theorem ==
Let $\struct {A, \ast, \norm {\, \cdot \,} }$ be a $\text C^\ast$-algebra.
Let $\le$ be the canonical preordering on $A$.
Let $a, b \in A$ be such that $a \le b$. 
Let $c \in A$.
Then $c^\ast a c \le c^\ast b c$.
== Proof ==
Since $a \le b$, we have that $b - a$ is positive.
Hence $c^\ast \paren {b - a} c$ is positive by Conjugation in C*-Algebra preserves Positivity.
Hence $c^\ast b c - c^\ast a c$ is positive.
By the definition of $\le$, we have $c^\ast a c \le c^\ast b c$. 
== Sources ==
* : $2.2$: Positive Elements of $C^\ast$-Algebras
Category:Conjugation in C*-Algebra preserves Positivity
Conjugation of Bijection between Symmetric Groups is Isomorphism

== Theorem ==
Let $A$ and $B$ be sets
Let $f$ be a bijection from $E$ to $F$.
Let $S_A$ and $S_B$ denote the set of all permutations on $A$ and $B$ respectively.
Let $\Phi: S_A \to S_B$ be the mapping defined as:
:$\forall u \in S_A: \map \Phi u = f \circ u \circ f^{-1}$
where $\circ$ denotes composition of mappings.
Then $\Phi$ is an isomorphism from $S_A$ to $S_B$.
== Proof ==
We have that $\struct {S_A, \circ}$ and $\struct {S_B, \circ}$ are the symmetric group on $S_A$ and $S_B$ respectively.
Hence we are about to prove that $\Phi$ is actually a group isomorphism.
Because $f$ is a bijection it follows from Inverse of Bijection is Bijection that $f^{-1}$ is also a bijection.
From Composite of Bijections is Bijection, it follows that $f \circ u \circ f^{-1}$ is also a bijection.
As $f \circ u \circ f^{-1}$ is from $S_B$ to $S_B$, it follows by definition that $f \circ u \circ f^{-1}$ is in fact a permutation on $B$.
Hence $\Phi$ maps a permutation on $A$ to a permutation on $B$, as stated by the question.
Let $u$ and $v$ be arbitrary permutations on $A$.
Then:
This demonstrates that $\Phi$ is a (group) homomorphism.
Let $u, v \in S_A$ such that $u = v$.
Then:
So we have:
:$\map \Phi u = \map \Phi v \implies u = v$
and by definition $\Phi$ is injective.
Let $w \in S_B$.
Let $g: S_A \to S_B$ be defined as:
:$g := f^{-1} \circ w \circ f$
Then from Inverse of Bijection is Bijection and Composite of Bijections is Bijection as above:
:$g$ is a bijection from $S_A$ to $S_B$.
Thus we have:
Thus $\forall w \in S_B: \exists g \in S_A: \map \Phi g = w$
That is: $\Phi$ surjective.
Thus $\Phi$ has been shown to be a bijective (group) homomorphism.
Hence the result.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups: Exercise $7.5$
Category:Symmetric Groups
Category:Examples of Group Isomorphisms
Conjunction and Conditional

== Theorems ==
=== Conjunction is Equivalent to Negation of Conditional of Negative ===
=== Conditional is Equivalent to Negation of Conjunction with Negative ===
=== Conjunction with Negative is Equivalent to Negation of Conditional ===
=== Modus Ponendo Tollens ===
== Law of Excluded Middle ==
Note that the Modus Ponendo Tollens:
:$\neg \paren {p \land q} \dashv \vdash p \implies \neg q$
can be proved in both directions without resorting to Law of Excluded Middle.
All the others:
:$p \land q \vdash \neg \paren {p \implies \neg q}$
:$p \implies q \vdash \neg \paren {p \land \neg q}$
:$p \land \neg q \vdash \neg \paren {p \implies q}$
are not reversible in intuitionistic logic.
== Also see ==
* Negation of Conditional implies Antecedent‎
* Negation of Conditional implies Negation of Consequent‎
Category:Conjunction
Category:Conditional
Conjunction has no Inverse

== Theorem ==
Let $\land$ denote the conjunction operation of propositional logic.
Then there exists no binary logical connective $\circ$ such that:
:$(1): \quad \forall p, q \in \set {T, F}: \left({p \land q}\right) \circ q = p$
== Proof ==
This will be proven by contradiction.
Let such an operation $\circ$ exist.
Let $f^\circ: \mathbb B^2 \to \mathbb B$ be the associated truth function.
Suppose now that $q = F$, while $p$ remains unspecified.
Then:
:$p \land q = \map {f^\land} {p, F} = F$
where $f^\land$ is the truth function of conjunction.
It does not matter what $p$ is, for:
:$\map {f^\land} {T, F} = \map {f^\land} {F, F} = F$
Hence, for $\paren {p \land q} \circ q = p$ to hold, $f^\circ$ must satisfy:
:$\map {f^\circ} {F, F} = p$
However, because $p$ could still be either $T$ or $F$, this identity cannot always hold.
Therefore, $\circ$ cannot exist.
Category:Conjunction
Conjunction iff Biconditional of Biconditional with Disjunction

== Theorem ==
:$p \land q \dashv \vdash \paren {p \iff q} \iff \paren {p \lor q}$
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the appropriate truth values match for all boolean interpretations.
$\begin{array}{|ccc||ccccccc|} \hline
p & \land & q & (p & \iff & q) & \iff & (p & \lor & q) \\
\hline
\F & \F & \F & \F & \T & \F & \F & \F & \F & \F \\
\F & \F & \T & \F & \F & \T & \F & \F & \T & \T \\
\T & \F & \F & \T & \F & \F & \F & \T & \T & \F \\
\T & \T & \T & \T & \T & \T & \T & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S 2.10$: Exercise $2.6$
Category:Biconditional
Category:Conjunction
Category:Disjunction
Conjunction implies Disjunction/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective is true for all boolean interpretations.
:$\begin{array}{|ccc|c|ccc|} \hline
(p & \land & q) & \implies & (p & \lor & q) \\
\hline
\F & \F & \F & \T & \F & \F & \F \\
\F & \F & \T & \T & \F & \T & \T \\
\T & \F & \F & \T & \T & \T & \F \\
\T & \T & \T & \T & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S1.2$: Some Remarks on the Use of the Connectives and, or, implies: Exercise $3$
Category:Conjunction implies Disjunction
Conjunction in terms of NAND

== Theorem ==
:$p \land q \dashv \vdash \paren {p \uparrow q} \uparrow \paren {p \uparrow q}$
where $\land$ denotes logical conjunction and $\uparrow$ denotes logical NAND.
== Proof ==
== Sources ==
* : $\S 2.5$: Further Logical Constants
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(5)$
* : $\S 2.4.2$
Category:Logical NAND
Category:Conjunction
Conjunction is Equivalent to Negation of Conditional of Negative/Formulation 1

== Theorem ==
:$p \land q \dashv \vdash \neg \paren {p \implies \neg q}$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof by Truth Table ==
== Sources ==
* : $\S 2.4$: Relations between Truth-Functions
* : Chapter $1$: The Propositional Calculus $1$: $5$ Further Proofs: Résumé of Rules: Exercise $1 \ \text{(e)}$
* : $\S 2.3.3$
Category:Conjunction is Equivalent to Negation of Conditional of Negative
Conjunction is Equivalent to Negation of Conditional of Negative/Formulation 1/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connectives match for all boolean interpretations.
$\begin{array}{|ccc||ccccc|} \hline
p & \land & q & \neg & (p & \implies & \neg & q) \\
\hline
\F & \F & \F & \F & \F & \T & \T & \F \\
\F & \F & \T & \F & \F & \T & \F & \T \\
\T & \F & \F & \F & \T & \T & \T & \F \\
\T & \T & \T & \T & \T & \F & \F & \T \\
\hline
\end{array}$
Category:Conjunction is Equivalent to Negation of Conditional of Negative
Category:Truth Table Proofs
Conjunction is Equivalent to Negation of Conditional of Negative/Formulation 2

== Theorem ==
:$\vdash \paren {p \land q} \iff \paren {\neg \paren {p \implies \neg q} }$
== Proof 1 ==
== Proof by Truth Table ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 3$: Theorem $\text{T38}$
Category:Conjunction is Equivalent to Negation of Conditional of Negative
Conjunction is Equivalent to Negation of Conditional of Negative/Formulation 2/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective are true for all boolean interpretations.
$\begin{array}{|ccc|c|ccccc|} \hline
(p & \land & q) & \iff & (\neg & (p & \implies & \neg & q)) \\
\hline
\F & \F & \F & \T & \F & \F & \T & \T & \F \\
\F & \F & \T & \T & \F & \F & \T & \F & \T \\
\T & \F & \F & \T & \F & \T & \T & \T & \F \\
\T & \T & \T & \T & \T & \T & \F & \F & \T \\
\hline
\end{array}$
== Sources ==
* : $\S \text{I}: 13$: Logical Equivalences: Exercise $\text{(A)} \ 4$
Category:Truth Table Proofs
Category:Conjunction is Equivalent to Negation of Conditional of Negative
Conjunction of Finite State Machines

== Theorem ==
Let $\Sigma$ be a finite set.
Let $F_1 = \tuple {S_1, A_1, I_1, \Sigma, T_1}$ and $F_2 = \tuple {S_2, A_2, I_2, \Sigma, T_2}$ be finite state machines.
Then there exists a finite state machine $F$ such that $\map L F = \map L {F_1} \cap \map L {F_2}$.
== Proof ==
Construct $F = \tuple {S_1 \times S_2, A_1 \times A_2, \tuple {I_1, I_2}, \Sigma, T}$ where:
:$\map T {s_1, s_2, \Sigma} = \tuple {\map {T_1} {s_1}, \map {T_2} {s_2} }$
The machines are simultaneously emulated in the first and second components of the state tuple.
When the input word is exhausted, $F$ accepts both $F_1$ and $F_2$ are in an accepting state, as required.
Category:Abstract Machines
Conjunction with Contradiction/Proof 2

== Theorem ==
== Proof ==
We apply the Method of Truth Tables to the proposition.
As can be seen by inspection, in each case, the truth values in the appropriate columns match for all boolean interpretations.
$\begin{array}{|c|ccc||c|ccc|} \hline
\bot & p & \land & \bot & p \\
\hline
F & F & F & F & F \\
F & T & F & F & T \\
\hline
\end{array}$
Category:Conjunction with Contradiction
Conjunction with Law of Excluded Middle

== Theorem ==
:$\vdash p \iff \paren {p \land q} \lor \paren {p \land \neg q}$
== Proof ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Theorem $\text{T68}$
Category:Conjunction
Category:Law of Excluded Middle
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 1

== Theorem ==
:$p \land \neg q \dashv \vdash \neg \paren {p \implies q}$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof by Truth Table ==
== Sources ==
* : Chapter $2$: The Propositional Calculus $2$: $2$: Theorems and Derived Rules: Exercise $5 \ \text{(g)}$
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 1/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connectives match for all boolean interpretations.
$\begin{array}{|cccc||cccc|} \hline
p & \land & \neg & q & \neg & (p & \implies & q) \\
\hline
\F & \F & \T & \F & \F & \F & \T & \F \\
\F & \F & \F & \T & \F & \F & \T & \T \\
\T & \T & \T & \F & \T & \T & \F & \F \\
\T & \F & \F & \T & \F & \T & \T & \T \\
\hline
\end{array}$
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 2

== Theorem ==
:$\vdash \paren {p \land \neg q} \iff \paren {\neg \paren {p \implies q} }$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof 1 ==
== Proof by Truth Table ==
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 2/Forward Implication

== Theorem ==
:$\vdash \paren {p \land \neg q} \implies \paren {\neg \paren {p \implies q} }$
== Proof ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 3$: Theorem $\text{T42}$
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 2/Proof 1

== Theorem ==
== Proof ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 3$: Theorem $\text{T40}$
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Negative is Equivalent to Negation of Conditional/Formulation 2/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective is true for all boolean interpretations.
$\begin{array}{|cccc|c|cccc|} \hline
p & \land & \neg & q & \iff & \neg & (p & \implies & q) \\
\hline
\F & \F & \T & \F & \T & \F & \F & \T & \F \\
\F & \F & \F & \T & \T & \F & \F & \T & \T \\
\T & \T & \T & \F & \T & \T & \T & \F & \F \\
\T & \F & \F & \T & \T & \F & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S \text{I}: 7$: Determining the Truth Values of Complex Propositions
Category:Conjunction with Negative is Equivalent to Negation of Conditional
Conjunction with Tautology/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables to the proposition.
As can be seen by inspection, in each case, the truth values in the appropriate columns match for all boolean interpretations.
$\begin{array}{|c|ccc||c|} \hline
p & p & \land & \top & \top \\
\hline
\F & \F & \F & \T & \T \\
\T & \T & \T & \T & \T \\
\hline
\end{array}$
Category:Conjunction with Tautology
Conjunctive Normal Form/Examples

== Examples of Conjunctive Normal Form ==
:$\paren {p \lor q} \land \paren {p \lor \neg r} \land \paren {q \lor r}$
is in CNF.
:$\paren {\neg p \lor q \lor r} \land \paren {\paren {p \land \neg q} \lor r} \land \paren {\neg r}$
is not in CNF because there is a conjunction buried in the second disjunction.
:$\paren {\neg p \lor q \lor r} \land \neg \paren {\neg q \lor r} \land \paren {\neg r}$
is not in CNF because the second disjunction is negated.
:$p \land q$
is in CNF, as it is a conjunction of literals.
:$p \lor q$
is in CNF, as it is a trivial (one-element) conjunction of a disjunction of literals.
== Sources ==
* 
Category:Examples of Conjunctive Normal Form
Connected Component is Closed

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Then every connected component of $T$ is closed.
== Proof ==
Let $H$ be a connected component of $T$.
By the definition of connected component, $H$ is connected.
From Closure of Connected Set is Connected then the closure $H^-$ is connected.
By the definition of the closure, $H \subseteq H^-$.
By the definition of connected component, $H$ is a maximal connected set.
Hence $H = H^-$.
From Set is Closed iff Equals Topological Closure, $H$ is closed.
Category:Connected Sets
Category:Components
Connected Domain is Connected by Staircase Contours

== Theorem ==
Let $D \subseteq \C$ be an open set.
Then $D$ is a connected domain :
:for all $z, w \in \C$, there exists a staircase contour in $D$ with start point $z$ and end point $w$.
== Proof ==
=== Necessary Condition ===
Suppose $D$ is a connected domain.
If $z, w \in D$, there exists a path $\gamma: \closedint 0 1 \to D$ with $\map \gamma 0 = z$ and $\map \gamma 0 = w$.
From the Paving Lemma, it follows that there exist $\epsilon \in \R_{>0}$ and a subdivision $\set {x_0, x_1, \ldots, x_n}$ of $\closedint 0 1$ such that:
:$\ds \bigcup_{k \mathop = 0}^n \map {B_\epsilon} {\map \gamma {x_k} } \subseteq D$
and for all $k \in \set {0, 1, \ldots, n - 1}$:
:$\map \gamma {\closedint {x_k} {x_{k + 1} } } \subseteq \map {B_\epsilon} {\map \gamma {x_k} }$
where $\map {B_\epsilon} {\map \gamma {x_k} }$ is the open $\epsilon$-ball about $\map \gamma {x_k}$.
Let $\map \Re {x_{k + 1} - x_k}$ denote the real part of $x_{k + 1} - x_k$, and $\map \Im {x_{k + 1} - x_k}$ denote the imaginary part of $x_{k + 1} - x_k$.
For all $k \in \set {0, 1, \ldots, n - 1}$, define the smooth paths $\gamma_{2 k + 1}, \gamma_{2 k + 2}: \gamma: \closedint 0 1 \to D$ by:
:$\map {\gamma_{2 k + 1} } t = x_k + t \paren {\map \Re {x_{k + 1} - x_k} }$
:$\map {\gamma_{2 k + 2} } t = x_k + \map \Re {x_{k + 1} - x_k} + i t \paren {\map \Im {x_{k + 1} - x_k} }$
These are the line segments connecting $x_k$, $x_k + \map \Re {x_{k + 1} - x_k}$, and $x_{k + 1}$.
It follows that $x_k + \map \Re {x_{k + 1} - x_k} \in \map {B_\epsilon} {\map \gamma {x_k} }$, as:
Then Open Ball is Convex Set shows that $\map {\gamma_{2 k + 1} } t, \map {\gamma_{2 k + 2} } t \in \map {B_\epsilon} {\map \gamma {x_k} } \subseteq D$ for all $t \in \closedint 0 1$.
It follows that the images of $\gamma_{2k+1}$ and $\gamma_{2k+2}$ are subsets of $D$. 
Define $C_k$ as the directed smooth curve that is parameterized by $\gamma_k$.
Thus $C_{2 k - 1}$ has start point $x_{k - 1}$, and $C_{2 k}$ has end point $x_k$.
Define $C$ as the concatenation of $C_1, \ldots, C_{2n}$.
Then $C$ is a staircase contour in $D$ with start point $z$ and end point $w$.
:
Illustration of the open balls inside the connected domain $D$.
The path $\gamma$ between $w$ and $z$ is grey, and the constructed staircase contour $C$ is red.
=== Sufficient Condition ===
Suppose that for all $z, w \in \C$, there exists a staircase contour in $D$ with start point $z$ and end point $w$.
Let $\gamma: \closedint a b \to D$ be a parameterization of $C$, where $\closedint a b$ is a closed interval.
Then $\gamma$ is a path in $D$ with $\map \gamma a = z$ and $\map \gamma b = w$.
Define $\gamma_0: \closedint 0 1 \to D$ by $\map {\gamma_0} t = \map \gamma {a + t \paren {b - a} }$.
Then $\gamma_0$ is also a path in $D$ with $\map {\gamma_0} 0 = z$ and $\map {\gamma_0} 1 = w$.
By definition of path-connected, it follows that $D$ is path-connected.
Hence, $D$ is a connected domain.
== Sources ==
* $\S 5.1$
Category:Complex Analysis
Connected Equivalence Relation is Trivial

== Theorem ==
Let $S$ be a set.
Let $\RR$ be a relation on $S$ which is both connected and an equivalence relation.
Then $\RR$ is the trivial relation on $S$.
== Proof ==
By definition of equivalence relation, $\RR$ is an equivalence relation :
:$\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$
From Relation is Connected iff Union with Inverse and Diagonal is Trivial Relation:
:$\Delta_S \cup \RR^{-1} \cup \RR = S \times S$
Hence the result.
== Examples ==
Category:Connected Relations
Category:Equivalence Relations
Category:Trivial Relation
Category:Connected Equivalence Relation is Trivial
Connected Equivalence Relation is Trivial/Examples/Arbitrary Set of 4 Elements

== Example of Connected Equivalence Relation is Trivial ==
Let $V = \set {a, b, c, d}$.
Let $S \subseteq V \times V$ such that:
:$S = \set {\tuple {a, b}, \tuple {b, c}, \tuple {c, d} }$
Let $\RR$ be an equivalence relation on $V$ such that:
:$S \subseteq \RR$
Then $\RR$ is the trivial relation on $S$.
== Proof ==
By definition, $\RR$ is connected.
We also have that $\RR$ is an equivalence relation.
The result follows from Connected Equivalence Relation is Trivial.
== Sources ==
* : Appendix $\text{A}.2$: Cartesian Products and Relations: Problem Set $\text{A}.2$: $10$
Category:Connected Equivalence Relation is Trivial
Connected Graph/Examples/Arbitrary Example 1

== Example of Connected Graph ==
The following is an example of a connected graph with $5$ vertices and $6$ edges.
:
Vertex $C$ is adjacent to vertex $A$ but not to vertex $B$
There are $2$ paths of length $2$ from $B$ to $C$, that is $\tuple {B, A, C}$ and $\tuple {B, D, C}$
There are a several cycles, including $\tuple {B, D, E, B}$.
== Sources ==
* : $\S 2.3.4.1$: Free Trees
Category:Examples of Connected Graphs
Connected Graph is Tree iff Removal of One Edge makes it Disconnected

== Theorem ==
Let $G = \struct {V, E}$ be a connected simple graph.
Then $G$ is a tree :
:for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.
== Proof ==
=== Sufficient Condition ===
=== Necessary Condition ===
== Sources ==
* : $\S 2.3.4.1$: Free Trees: Theorem $\mathrm A$
Category:Connected Graph is Tree iff Removal of One Edge makes it Disconnected
Category:Connected Graphs
Category:Tree Theory
Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Necessary Condition

== Theorem ==
Let $G = \struct {V, E}$ be a connected simple graph such that:
:for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.
Then $G$ is a tree.
== Proof ==
Let $G$ be a connected simple graph such that for all edges $e$ of $G$, the edge deletion $G \setminus \set e$ is disconnected.
Hence, by definition, every edge of $G$ must be a bridge.
So by Condition for Edge to be Bridge, $G$ has no circuits.
Hence $G$ is a tree by definition.
Category:Connected Graph is Tree iff Removal of One Edge makes it Disconnected
Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Sufficient Condition/Proof 1

== Theorem ==
== Proof ==
Let $G$ be a tree.
Then by definition $G$ has no circuits.
From Condition for Edge to be Bridge, every edge of $G$ is a bridge.
Thus by definition of bridge, removing any edge of $G$ will disconnect $G$.
Category:Connected Graph is Tree iff Removal of One Edge makes it Disconnected
Connected Graph is Tree iff Removal of One Edge makes it Disconnected/Sufficient Condition/Proof 2

== Theorem ==
== Proof ==
Let $G$ be a tree.
Hence $G$ has no cycles.
Let $v, v' \in V$.
Let the edge $\set {v, v'}$ be removed.
 $G$ is still connected.
Then $v$ and $v'$ are connected.
By If Vertices are Connected then Path Exists between them, there is a path $\tuple {v, v_1, \ldots, v'}$ of length $2$ or more.
Hence $\tuple {v, v_1, \ldots, v', v}$ is a cycle in $G$.
This contradicts the statement that $G$ has no cycles.
The result follows by Proof by Contradiction.
== Sources ==
* : $\S 2.3.4.1$: Free Trees: Theorem $\mathrm A$
Category:Connected Graph is Tree iff Removal of One Edge makes it Disconnected