Graph Theory Flashcards

—card— ^fsrs-08016u

Define Graph

A graph $G$ is fundamentally an ordered triple $(V, E, \psi)$ consisting of a vertex set $V$, an edge set $E$, and an incidence function $\psi: E \to V \times V$. Often, a simplified notation $G=(V, E)$ is used.

Definition Variations In abstract graph theory, a graph $G = (V, E)$ is formally defined where $E \subseteq [V]^2$, meaning $E$ consists of 2-element subsets of $V$, typically excluding self-loops or parallel edges.

---card--- ^fsrs-dzewt2

Order of a Graph

• Order of a Graph ($|G|$ or $\nu(G)$): This is the number of vertices (or points) in the graph $G$. It is denoted by $|V|$. A graph with $p$ points (vertices) is called a $(p, q)$-graph.

---card--- ^fsrs-7gaucc

Size of a Graph

• Size of a Graph ($||G||$ or $\epsilon(G)$): This is the number of edges (or lines) in the graph $G$. It is denoted by $|E|$. A graph with $q$ lines (edges) is called a $(p, q)$-graph.

---card--- ^fsrs-y9wbr2

Degree of a garph

• Degree of a Vertex ($d_G(v)$ or $d(v)$): The degree of a vertex $v$ is the number of edges incident with $v$. If a self-loop is present, it is counted twice. In simple graphs (no loops or parallel edges), the degree $d(v)$ is equal to the number of neighbors of $v$, denoted $|N(v)|$.

---card--- ^fsrs-x8vjo0

Self Loop

An edge associated with single vertex is called self loop.

---card--- ^fsrs-ayj0lg

Parallel Edges

Multiple edges associated with same unordered pair of vertices.

---card--- ^fsrs-ldf53a

Simple Graph

A graph that contains neither self-loops nor parallel edges

---card--- ^fsrs-ym0zpg

Isolated Vertex

A vertex that has no incident edge, i.e $d(v)=0$

---card--- ^fsrs-7o4z9w

Pendant Vertex

A vertex with $d(v)=1$ is called Pendant Vertex. In any tree with two or more vertices, there are at least two pendant vertices.

---card--- ^fsrs-15w136

Internal Vertex

A vertex in a tree that is not Pendant Vertex is Internal Vertex.

---card--- ^fsrs-hlqkw5

Handshaking Theorem or Lemma

For a graph $G$ with $n$ vertices, a fundamental result (The First Theorem of Graph Theory, or Handshaking Lemma) states that the sum of the degrees of all vertices is equal to twice the number of edges: $$\sum_{v \in V(G)} d(v) = 2|E|$$

---card--- ^fsrs-3r9e7w

Proof of the Handshaking Theorem

Theorem Statement:

For any graph $G$, the sum of the degrees of all vertices is equal to twice the number of edges:

$$\sum_{v \in V(G)} d(v) = 2|E|$$

Proof Outline:

The proof relies on counting the total incidence between vertices and edges.

1. Let $S$ be the sum of the degrees of all vertices: $S = \sum d(v)$.
2. Consider an individual edge $e$. When calculating the total sum $S$, each edge contributes exactly 2 to $S$.
   • Non-loop edge: A normal edge contributes 1 to the degree of each of its two endpoints, resulting in a total contribution of $1 + 1 = 2$ to the sum $S$.
   • Loop: A self-loop contributes 2 to the degree of its single incident vertex (it counts twice in the degree calculation), resulting in a total contribution of 2 to the sum $S$.
3. Since every edge contributes exactly 2 to the total sum $S$, the sum of all degrees must be equal to twice the number of edges, $2|E|$.
4. Therefore, $S = 2|E|$.

---card--- ^fsrs-9pcjkl

Number of odd-degree vertices is always even.

Theorem: The Number of Odd-Degree Vertices is Always Even

Statement: The number of vertices with an odd degree in any graph $G$ is always even.

Proof:

1. The Handshaking Lemma states that the sum of the degrees of all vertices is equal to twice the number of edges: $\sum_{v \in V(G)} d(v) = 2|E|$.
2. Since $2|E|$ is always an even number, the total sum of degrees, $\sum_{v \in V(G)} d(v)$, must be even.
3. We can partition the vertices $V$ into two disjoint sets: $V_{\text{even}}$ (vertices with even degree) and $V_{\text{odd}}$ (vertices with odd degree).
4. The total degree sum can be written as the sum over these two sets: $$\sum_{v \in V} d(v) = \sum_{v \in V_{\text{even}}} d(v) + \sum_{v \in V_{\text{odd}}} d(v)$$
5. The sum of degrees of vertices in $V_{\text{even}}$ is a sum of even numbers, and thus $\sum_{v \in V_{\text{even}}} d(v)$ is even.
6. Since the total sum $\sum_{v \in V} d(v)$ is even (from step 2) and the sum over $V_{\text{even}}$ is even (from step 5), the remaining sum, $\sum_{v \in V_{\text{odd}}} d(v)$, must also be even.
7. For the sum of odd degrees to be an even number, there must be an even number of terms (vertices) in $V_{\text{odd}}$.

Therefore, the number of odd-degree vertices ($|V_{\text{odd}}|$) must be even.

---card--- ^fsrs-smid10

Degree Sequence and Graphical Sequence

The Degree Sequence is the list of vertex degrees of a graph, typically ordered from largest to smallest (non-increasing order). If a graph $G$ has $n$ vertices, its degree sequence is the $n$-tuple $(d_1, d_2, \dots, d_n)$, where $d_1 \ge d_2 \ge \dots \ge d_n$ are the degrees of its vertices.

A sequence of non-negative integers $S = (d_1, d_2, \dots, d_n)$ is called a Graphical Sequence if it can be realised as the degree sequence of some simple graph $G$.

For a sequence to be considered graphical, it must satisfy two necessary conditions:

1. Even Sum: The sum of all the degrees ($\sum d_i$) must be an even number (this follows directly from the Handshaking Lemma).
2. Degree Limits: Every degree $d_i$ must be less than or equal to $n-1$, where $n$ is the number of vertices ($0 \le d_i \le n - 1$).

---card--- ^fsrs-pwyjo5

Havel Hakimi Algorithm

The Havel-Hakimi Algorithm is a specific method used to determine if a given non-negative integer sequence is a Graphical Sequence—that is, if it can be the degree sequence of a simple graph.

Algorithm Steps

The algorithm repeatedly simplifies the sequence until either a clear conclusion is reached or all remaining elements are zero.

1. Sort: Sort the sequence $S = (d_1, d_2, \dots, d_n)$ in non-increasing (largest to smallest) order.
2. Remove Head: Remove the first element, $d_1$ (the largest degree).
3. Subtract: Subtract 1 from the next $d_1$ elements in the sequence.
4. Repeat: Repeat steps 1–3 until one of the following conditions is met:
   • Graphical: All remaining elements are zeros (the sequence is graphical).
   • Not Graphical: A negative number appears (the sequence is not graphical).

Necessary Conditions

Before applying Havel-Hakimi, a sequence must first satisfy two necessary conditions for graph realizability:

1. Even Sum (Handshaking Lemma): The sum of the degrees ($\sum d_i$) must be an even number.
2. Degree Bounds: Every degree $d_i$ must be less than or equal to $n-1$, where $n$ is the number of vertices ($0 \le d_i \le n - 1$).

---card--- ^fsrs-7r5t2j

Example of Havel-Hakimi Algorithm

A sequence might satisfy the necessary conditions but still fail the Havel-Hakimi test. For example, the sequence $S = (4, 4, 3, 2, 1)$ has an even sum (14) and valid bounds ($n=5$). However, applying the steps leads to a negative number, showing it is non-graphical:

1. (4, 4, 3, 2, 1) $\to$ Remove 4, subtract 1 from the next 4 elements.
2. (3, 2, 1, 0) $\to$ Sort: (3, 2, 1, 0).
3. Remove 3, subtract 1 from the next 3 elements.
4. (1, 0, -1) $\to$ Result: A negative number appears, so it is not graphical.

---card--- ^fsrs-v9czbv

Neighbours of a Graph

Two vertices $x, y$ of a graph $G$ are called neighbours if ${x, y}$ is an edge of $G$. The set of neighbours of a vertex $v$ in $G$ is denoted by $N_G(v)$, or briefly $N(v)$.

---card--- ^fsrs-qvr588

Open Neighbourhood $N(v)$

This is the set of vertices $x$ such that $vx$ is an edge. In simple graphs, the degree of a vertex $v$, $d(v)$, is equal to the number of its neighbours, denoted $|N(v)|$.

---card--- ^fsrs-6fg9zt

Closed Neighbourhood $N[v]$

This set includes the vertex $v$ itself along with its open neighbourhood: $N[v] = N(v) \cup {v}$.

---card--- ^fsrs-vwb0lg

Define Subgraph

A subgraph $g$ (or $G'$) of a graph $G$ is defined by containment of its vertex and edge sets.

Specifically, $g$ is a subgraph of $G$ if:

1. The vertex set of $g$ is a subset of $G$'s vertex set ($V(g) \subseteq V(G)$).
2. The edge set of $g$ is a subset of $G$'s edge set ($E(g) \subseteq E(G)$).
3. Each edge in $g$ must be associated with the same end vertices as it is in $G$.

We write $G' \subseteq G$ to denote that $G'$ is a subgraph of $G$. If $G' \ne G$, $G'$ is a proper subgraph.

---card--- ^fsrs-z1c1mb

Define Induced Subgraphs

The Induced Subgraph is a special type of subgraph that is created solely by selecting a subset of vertices and keeping all the edges from the original graph that connect those selected vertices.

Here are the key points regarding induced subgraphs:

• Definition: For a graph $G=(V, E)$ and a subset of vertices $V' \subseteq V$, the induced subgraph, denoted $G[V']$ or $G[S]$, consists of the vertex set $V'$ and the edge set $E'$ containing precisely all the edges of $G$ whose both endpoints lie in $V'$.
• Edge Set Condition: The edge set of an induced subgraph $H$ (induced by $V(H)$) must contain all the edges of the original graph $G$ whose endpoints are both in $V(H)$. $E(H) = E(G) \cap E(V(H))$.
• Creation Method: An induced subgraph is obtained from the original graph $G$ by deleting only vertices and the edges incident to them; no other edges are removed.

---card--- ^fsrs-4hpjg2

What is Spanning Sub graph?

A Spanning Subgraph is a subgraph $H$ of a graph $G$ that contains all the vertices of the original graph $G$.

Definition

A graph $G'$ is a spanning subgraph of $G$ if:

1. All vertices of $G'$ are in $G$, and $V(G') = V(G)$.
2. The edge set of $G'$ is a subset of $G$'s edge set ($E(G') \subseteq E(G)$).

Less formally, a spanning subgraph "spans" or covers all vertices of $G$, but may have fewer edges. Spanning trees are critical examples of spanning subgraphs.

---card--- ^fsrs-a4jgy5

Complete Graphs

A Complete Graph ($K_n$) is a simple graph where every distinct pair of vertices is connected by an edge.

Here are the key properties of a complete graph $K_n$:

• Definition: It is a simple graph where every pair of distinct vertices is adjacent.
• Order: It has $n$ vertices.
• Regularity: It is an $(n-1)$-regular graph, meaning every vertex has a degree of $n-1$.
• Size (Edges): The total number of edges in $K_n$ is $\frac{n(n-1)}{2}$.
  • For example, a complete graph of four vertices, $K_4$, has 6 edges.
  • $K_5$ has 5 vertices and 10 edges.
• Components/Properties: A $K_3$ is called a triangle. Induced subgraphs of complete graphs are also complete.

---card--- ^fsrs-7rinte

Total number of Edges in $K_n$

1. Vertex Degree in $K_n$ A complete graph $K_n$ is a simple graph with $n$ vertices where every vertex is adjacent to every other vertex. Since there are $n$ vertices, every vertex has a degree of $n-1$. $K_n$ is an $(n-1)$-regular graph.
2. Apply the Handshaking Lemma The Handshaking Lemma states that the sum of the degrees of all vertices ($\sum d(v)$) is equal to twice the number of edges ($2|E|$). $$\sum_{v \in V(G)} d(v) = 2|E|$$
3. Calculate the Total Sum of Degrees Since there are $n$ vertices, and each has degree $(n-1)$, the total sum of degrees is: $$\sum d(v) = n \cdot (n-1)$$
4. Solve for the Number of Edges By equating the results from steps 2 and 3: $$2|E| = n(n-1)$$ $$|E| = \frac{n(n-1)}{2}$$

This quantity is also represented by the binomial coefficient $\binom{n}{2}$.

---card--- ^fsrs-lkudtd

Define Regular Graph

A Regular Graph is a graph in which all vertices have the same degree.

• If every vertex in the graph has a degree equal to some integer $k$, the graph is called $k$-regular.
• For example, a complete graph $K_n$ is a regular graph, specifically $(n-1)$-regular.
• A 3-regular graph is known as a cubic graph.

---card--- ^fsrs-kpbtv0

Aurther Cayley Theorem

The theorem states that the total number of distinct labeled trees with $n$ vertices (where $n \ge 2$) is $n^{n-2}$.

---card--- ^fsrs-qnr610

Matrix-Tree Theorem or Kirchhoff Theorem

The theorem confirms that the total number of spanning trees in a connected, labeled graph $G$ is equal to the value of any cofactor of its Laplacian matrix, $L = D - A$.

Key Matrix Definitions:

• Laplacian Matrix ($L$): This matrix is derived from the graph's structure. For a graph with adjacency matrix $A$ (or $X$) and diagonal degree matrix $D$, the Laplacian is $D - A$ (or $D - X$).
• Result: All cofactors of this matrix are equal, and that common value is the number of spanning trees in $G$.

---card--- ^fsrs-xkdrnx

Bipartite Graphs ($K_{m,n}$)

A Bipartite Graph $G$ is a graph whose vertex set $V$ can be partitioned into two disjoint subsets, $V_1$ and $V_2$, such that every edge in the graph connects a vertex in $V_1$ to a vertex in $V_2$.

Key Properties

• Partitioning: The vertex set $V$ is the union of the two disjoint subsets ($V = V_1 \cup V_2$ and $V_1 \cap V_2 = \emptyset$). The pair $(V_1, V_2)$ is called the bipartition of $G$.
• Edge Rule: No edges exist between vertices within the same subset ($V_1$ or $V_2$).
• Coloring: A bipartite graph is also known as a 2-partite or a 2-chromatic graph, as it is 2-colorable.
• Cycles: A graph is bipartite if and only if it contains no odd-length cycles (a cycle of odd length).

---card--- ^fsrs-2uappr

Complete Bipartite Graphs

• Definition: This is a bipartite graph where every vertex in the first set ($V_1$ with size $m$) is connected to every vertex in the second set ($V_2$ with size $n$).
• Order and Size: In $K_{m,n}$, the total number of vertices (order) is $m+n$, and the total number of edges (size) is $m \times n$.

---card--- ^fsrs-fofost

Properties of the Complete Bipartite Graphs

A Complete Bipartite Graph ($K_{m,n}$ or $K_{s,t}$) has the following core properties:

• Partitioning: Its vertex set $V$ is partitioned into two disjoint subsets, $V_1$ (size $m$) and $V_2$ (size $n$). Every edge connects a vertex in $V_1$ to a vertex in $V_2$.
• Adjacency: Every vertex in $V_1$ is connected to every vertex in $V_2$. There are no edges between vertices within the same subset.
• Order (Vertices): The total number of vertices (order) is $m+n$.
• Size (Edges): The total number of edges (size) is $m \times n$.
• Degree: A vertex in $V_1$ has degree $n$, and a vertex in $V_2$ has degree $m$.
• Coloring: It is a 2-colorable graph.
• Cycles: It contains no odd-length cycles.
• Connectivity: It is a simple and connected graph, provided $m, n \ge 1$.

---card--- ^fsrs-47id18

What is Graph Isomorphism?

Two graphs, $G$ and $G'$ (or $H$), are said to be isomorphic (denoted $G \cong G'$ or $G \sim H$) if there exists a one-to-one correspondence (a bijection) between their vertices and between their edges such that the incidence relationship is preserved.

In simpler terms:

• If edge $e$ is incident on vertices $v_1$ and $v_2$ in $G$, the corresponding edge $e'$ in $G'$ must be incident on the vertices $v'_1$ and $v'_2$ that correspond to $v_1$ and $v_2$, respectively.
• Any two vertices $u, v \in V(G)$ are adjacent in $G$ if and only if their corresponding images, $f(u)$ and $f(v)$, are adjacent in $H$.

We do not normally distinguish between isomorphic graphs.

Properties of Isomorphic Graphs

If two graphs are isomorphic, they must satisfy certain mathematical properties:

1. Same Number of Vertices (Order): $|V(G)| = |V(H)|$.
2. Same Number of Edges (Size): $|E(G)| = |E(H)|$.
3. Same Degree Sequence: They must have an equal number of vertices with a given degree.
4. Preserved Adjacency: The adjacency and non-adjacency relations must be preserved.

Important Note: These conditions (1, 2, and 3) are necessary, but they are not sufficient to prove isomorphism. Finding a simple and efficient criterion for detecting isomorphism is an important unsolved problem in graph theory.

---card--- ^fsrs-5to4qh

What is complementery of a Graph?

The complement of a graph $G$ (often denoted $\bar{G}$ or $G$ in some texts) is a graph built on the same vertex set $V$.

The edge set of the complement, $E(\bar{G})$, consists of exactly those edges that are not present in $G$.

Key Properties

• Structure: The complement $\bar{G}$ is the graph on $V$ whose edge set is all possible pairs of vertices $[V]^2$ excluding the edges of $G$.
• Relationship: $G$ and its complement $\bar{G}$ together form a complete graph on $V(G)$.

---card--- ^fsrs-usv61c

Self Complementry Graph

Self-Complementary: A graph $G$ is defined as self-complementary if it is isomorphic to its own complement ($G \cong \bar{G}$). If a graph $G$ has $n$ vertices and is self-complementary, then $n(n-1)/4$ must be an integer, meaning $n$ must satisfy $n \equiv 0$ or $1 \pmod 4$.

---card--- ^fsrs-9wehou

Define Walk, Trail and Path

Walk

A walk is a finite alternating sequence of vertices and edges, beginning and ending with vertices.

• If the walk starts and ends at the same vertex, it is a closed walk.
• A walk may also be referred to as an edge train or a chain.

Trail

A trail is a walk in which all the edges (or lines) are distinct.

• An Eulerian path (or Euler trail) is a trail that visits every edge exactly once.

Path

A path is a trail in which all the vertices (or points) are distinct.

• A path does not intersect itself.
• The length of a path is the number of edges it contains.

---card--- ^fsrs-3kluja

Define Eulerian Path, Eulerian Circuit, and Eulerian Graph

Eulerian Path and Circuit

1. Eulerian Path (Euler Trail): An Eulerian path is a walk in a graph that traverses every edge (line) exactly once. An open walk that covers all edges of a graph without retracing any edge is called a unicursal line or an open Euler line.
2. Eulerian Circuit (Euler Cycle/Tour): An Eulerian circuit is a closed walk that traverses every edge exactly once. It must start and end at the same vertex.

Eulerian Graph

An Eulerian Graph is a graph that contains an Eulerian circuit. Since the Euler line contains all edges, an Euler graph is always connected, assuming no isolated vertices.

[!note] Eulerian: Can I trace this drawing without lifting my pen or repeating lines?

---card--- ^fsrs-rgmf8d

Euler Theorem

Euler's Theorem states that a connected undirected graph $G$ has an Eulerian circuit if and only if every vertex in $G$ has an even degree.

A connected undirected graph $G$ has an Eulerian path (but not a circuit) if and only if exactly two vertices have an odd degree. A graph that has such a path is sometimes called a unicursal graph.

---card--- ^fsrs-iba3ct

What is Hamiltonian Path, Cycle and Graph?

• Hamiltonian Path: A path in a graph that visits every vertex exactly once. In a connected graph with $n$ vertices, the length of a Hamiltonian path is $n-1$.
• Hamiltonian Cycle (or Circuit): A cycle (a closed walk) that traverses every vertex of the graph exactly once. If a graph has $n$ vertices, a Hamiltonian circuit consists of exactly $n$ edges.
• Hamiltonian Graph: A graph is called Hamiltonian if it contains a Hamiltonian cycle.

[!note] • Hamiltonian: Can I visit all cities exactly once on my road trip?

---card--- ^fsrs-fd70iz

Dirac's Theorem

If $G$ is a simple graph with $n \ge 3$ vertices and the minimum degree of every vertex is at least $n/2$, then $G$ is a Hamiltonian graph (i.e., it has a Hamilton cycle or circuit).

This condition is sufficient, but not necessary, for a graph to be Hamiltonian.

---card--- ^fsrs-vlmvkk

Ore's Theorem

The theorem specifies that if $G$ is a simple graph with $n \ge 3$ vertices, and for every pair of non-adjacent vertices $u$ and $v$, the sum of their degrees is at least $n$:

$$\deg(u) + \deg(v) \ge n$$

then $G$ is Hamiltonian (i.e., it contains a Hamiltonian cycle).

This theorem is closely related to Dirac's Theorem, which uses the minimum degree of all vertices. Would you like to compare the conditions of Ore's Theorem and Dirac's Theorem?

---card--- ^fsrs-rrikvj

Graph with 6 vertices

1. Which is Hamiltonian but not Eulerian
2. Which is Eularian but not Hamiltonian

graph TD
    subgraph "Graph 1: Hamiltonian but NOT Eulerian"
        A1((A)) --- B1((B))
        B1 --- C1((C))
        C1 --- D1((D))
        D1 --- E1((E))
        E1 --- F1((F))
        F1 --- A1
        A1 --- C1
        A1 --- D1
    end
subgraph "Graph 2: Eulerian but NOT Hamiltonian"
    A2((A)) --- B2((B))
    B2 --- C2((C))
    C2 --- A2
    A2 --- D2((D))
    D2 --- E2((E))
    E2 --- A2
    A2 --- F2((F))
    F2 --- B2
end

—card— ^fsrs-lqpocp

Eulerian vs Hamiltonian

The study of Eulerian graphs originated with Leonhard Euler's solution to the Königsberg Bridge Problem in 1736. Hamiltonian circuits were named after Sir William Rowan Hamilton, who posed a puzzle related to visiting all vertices of the dodecahedron graph.

---card--- ^fsrs-m61smh

Prove: Impossible to have 9 people where each knows exactly 5 others

Proof: Impossibility of $9$ People with $5$ Acquaintances Each

1. Model the Problem as a Graph: We represent the $9$ people as vertices ($n=9$) and the relationship "knows" as an edge. Since the relationship is mutual, the resulting graph $G$ is undirected. The constraint is that every person knows exactly $5$ others, meaning the graph is $5$-regular (the degree of every vertex is $d(v)=5$).
2. Apply the Handshaking Lemma: The Handshaking Lemma (First Theorem of Graph Theory) states that for any graph $G$, the sum of the degrees of all vertices is equal to twice the number of edges: $\sum_{v \in V(G)} d(v) = 2|E|$.
3. Calculate the Sum of Degrees:
   • The graph has $n=9$ vertices.
   • The degree of every vertex is $d(v)=5$.
   • The sum of the degrees is $\sum d(v) = 9 \times 5 = 45$.
4. Check for Consistency: According to the Handshaking Lemma, $45$ must equal $2|E|$.
   • $2|E| = 45$
   • $|E| = 45 / 2 = 22.5$
5. Conclusion: The number of edges ($|E|$) must be an integer, as an edge represents a single relationship. Since $22.5$ is not an integer, a graph where every vertex has degree 5 and there are 9 vertices cannot exist. Therefore, it is impossible to have 9 people where each knows exactly 5 others.

This impossibility is also guaranteed by the theorem that the number of odd-degree vertices in any graph must always be an even number. Here, all 9 vertices have an odd degree (5), violating this requirement.

Does this proof make sense, or would you like to explore another theorem, such as those related to coloring or matching?

---card--- ^fsrs-fmmxiw

Define Tree

A tree is fundamentally defined as a connected graph that contains no circuits. Since circuits are forbidden, a tree must be a simple graph, having neither self-loops nor parallel edges.

A graph $G$ with $n$ vertices is a tree if and only if it satisfies any of the following equivalent conditions:

1. It is connected and circuitless.
2. It is connected and has exactly $n-1$ edges.
3. It is circuitless (acyclic) and has exactly $n-1$ edges.
4. There is one and only one path between every pair of its vertices.
5. It is a minimally connected graph (meaning the removal of any single edge disconnects it).

---card--- ^fsrs-wmwliu

There is one and only one path between every pair of vertices in a tree T

Proof

Let $T$ be a tree, and let $a$ and $b$ be any two distinct vertices in $T$.

1. Existence of at least one path: Since $T$ is defined as a connected graph, there must exist at least one path between every pair of vertices $a$ and $b$ in $T$.
2. Uniqueness (at most one path): Suppose, for contradiction, that there are two distinct paths between vertices $a$ and $b$. The union of these two distinct paths would necessarily contain a circuit (or cycle). However, by definition, a tree is a graph that contains no circuits. The existence of a circuit contradicts the definition of $T$ being a tree.

Therefore, there can be one and only one path between every pair of vertices in a tree $T$.

---card--- ^fsrs-7z3j5h

Prove that A tree with n vertices has n − 1 edges.

Proof by Induction

1. Base Cases:
   • For $n=1$, a tree has 0 edges, and $n-1 = 0$. (True).
   • For $n=2$, a tree has 1 edge, and $n-1 = 1$. (True).
2. Inductive Hypothesis: Assume the theorem is true for all trees with fewer than $n$ vertices.
3. Inductive Step: Let $T$ be a tree with $n$ vertices. Select any edge, $e_k$, in $T$. Since there is exactly one path between every pair of vertices in a tree (a consequence of the definition of a tree, as we discussed previously), the deletion of $e_k$ from $T$ will disconnect the graph.The resulting graph, $T - e_k$, consists of exactly two components (or subgraphs), $T_1$ and $T_2$. Since $T$ was circuitless, $T_1$ and $T_2$ are also trees, each having fewer than $n$ vertices.Let $T_1$ have $n_1$ vertices and $T_2$ have $n_2$ vertices. We know that $n_1 + n_2 = n$.By the Inductive Hypothesis, $T_1$ must have $n_1 - 1$ edges, and $T_2$ must have $n_2 - 1$ edges.The total number of edges in $T$ is the sum of the edges in $T_1$ and $T_2$ plus the single removed edge, $e_k$: $$|E(T)| = (n_1 - 1) + (n_2 - 1) + 1$$ $$|E(T)| = n_1 + n_2 - 1$$Since $n_1 + n_2 = n$: $$|E(T)| = n - 1$$

Thus, a tree with $n$ vertices has $n-1$ edges.

---card--- ^fsrs-ul4huj

Define Minimally Connected Graph

A minimally connected graph is a connected graph such that the removal of any single edge disconnects the graph.

This property is, in fact, an equivalent definition of a tree . A graph $G$ is a tree if and only if it is minimally connected.

Key Takeaways:

1. If a graph is a tree, the removal of any one edge disconnects it.
2. If a graph is minimally connected, it cannot contain a circuit, because removing an edge from a circuit would leave the graph connected. Since it is connected by definition and has no circuits, it is a tree.

---card--- ^fsrs-98bwh9

Five Equivalent Definitions of Tree

The five equivalent definitions of a tree, for a graph $G$ with $n$ vertices, are:

1. Connected and Circuitless: $G$ is a connected graph that contains no circuits (it is acyclic).
2. Connected with $n-1$ Edges: $G$ is connected and has exactly $n-1$ edges.
3. Circuitless with $n-1$ Edges: $G$ is circuitless (acyclic) and has exactly $n-1$ edges.
4. Unique Path: There is exactly one path between every pair of vertices in $G$.
5. Minimally Connected: $G$ is a minimally connected graph, meaning the removal of any single edge disconnects it.

---card--- ^fsrs-u9wqdl

A tree with two or more vertices has at least two pendant vertices.

A pendant vertex is defined as a vertex with a degree of one. Pendant vertices are also referred to as leaves.

Theorem: A tree with two or more vertices has at least two pendant vertices.

This can be proven using the Handshaking Lemma (Theorem 1.2.1) and the property that a tree $T$ with $n$ vertices has $n-1$ edges.

Proof:

1. Let $T$ be a tree with $n$ vertices, where $n \ge 2$.
2. The number of edges in $T$ is $e = n-1$.
3. The sum of the degrees of all vertices in $T$ must equal twice the number of edges (Handshaking Lemma): $$\sum_{v \in V(T)} d(v) = 2|E| = 2(n-1)$$.
4. In any tree, since there are $n-1$ edges and $n$ vertices, no vertex can have a degree of zero.
5. Suppose, for contradiction, that $T$ has at most one pendant vertex (i.e., at most one vertex with degree 1).
6. This means that $n-1$ of the vertices must have a degree of 2 or more, except for the single possible pendant vertex (degree 1).
7. The sum of the degrees under this assumption would be at least: $$\sum d(v) \ge 1 + 2(n-1) = 2n - 1$$.
8. Since we know that $\sum d(v)$ must equal $2n - 2$, the statement $2n - 2 \ge 2n - 1$ is false. This contradicts the Handshaking Lemma.

Therefore, every tree with $n \ge 2$ vertices must have at least two pendant vertices.

---card--- ^fsrs-owzbsb

Distance in Graph

The distance $d(u, v)$ between two vertices $u$ and $v$ in a connected graph $G$ is defined as the length of the shortest path between them.

Here are the key aspects of distance:

1. Length: In an unweighted graph, the length is the number of edges in the shortest path. In a weighted graph (such as a transport network), the length of a path is the sum of the weights or lengths of its edges.
2. Disconnected Graphs: If no path exists between $u$ and $v$, the distance is defined as $\infty$.
3. Metric: The distance between vertices of a connected graph is considered a metric, meaning it satisfies properties like nonnegativity, symmetry, and the triangle inequality.

---card--- ^fsrs-0nnwmi

Distance in a connected graph is a Metric

The distance $d(u, v)$ between two vertices $u$ and $v$ in a connected graph $G$ is the length of the shortest path between them. In an unweighted graph, this length is the number of edges in that shortest path.

The distance function $d(u, v)$ in a connected graph is a metric if it satisfies three specific requirements.

Theorem: Distance in a connected graph is a metric.

The distance $d(u, v)$ satisfies the following three metric properties:

1. Nonnegativity: $d(u, v) \ge 0$, and $d(u, v) = 0$ if and only if $u = v$.
   • Proof: The length of a path (number of edges) must be non-negative. A path of length zero only exists from a vertex to itself, $d(u, u)=0$.
2. Symmetry: $d(u, v) = d(v, u)$.
   • Proof: If $P$ is a shortest path from $u$ to $v$, then traversing the edges of $P$ in reverse order forms a path of the same length from $v$ to $u$. Therefore, the shortest path length must be the same in both directions.
3. Triangle Inequality: $d(u, v) \le d(u, w) + d(w, v)$ for any vertex $w$.
   • Proof: The shortest path between vertices $u$ and $v$ cannot be longer than an alternative path that passes through a specified vertex $w$. Any path from $u$ to $v$ passing through $w$ has a length equal to the sum of the path lengths $u$ to $w$ and $w$ to $v$. Since $d(u, v)$ is the shortest path length, it must be less than or equal to the sum of the shortest paths $d(u, w)$ and $d(w, v)$.

Since all three conditions are satisfied, the distance between vertices of a connected graph is a metric.

---card--- ^fsrs-k6oc61

Define Eccentricity and Centers

Eccentricity and the Center are concepts derived from the shortest path distance in a graph.

Eccentricity

The eccentricity $E(v)$ (also referred to as the associated number or separation) of a vertex $v$ in a graph $G$ is the distance from $v$ to the vertex farthest from $v$ in $G$.

Formally, the eccentricity $E(v)$ is defined as: $$E(v) = \max{d(v, u) \text{ for all } u \in G}$$ where $d(v, u)$ is the distance between $v$ and $u$.

Centers

A center of a graph $G$ is a vertex with the minimum eccentricity. The set of all central points is called the center of $G$.

• The eccentricity of a center, which is the minimum eccentricity, is called the radius $rad(G)$ of the graph.
• The maximum eccentricity is the diameter $diam(G)$ of the graph.
• The relationship between them is $rad(G) \le diam(G) \le 2 rad(G)$.

Centers in Trees

In the special case of a tree $T$:

• A tree $T$ has either ** one center or two adjacent centers**.
• The center(s) of a tree can be found by repeatedly removing all pendant vertices (leaves) until only 1 or 2 vertices remain.

The process of finding the center(s) relies on the observation that the maximum distance from a vertex $v$ occurs when the farthest vertex $u$ is a pendant vertex. The removal of all pendant vertices uniformly reduces the eccentricities of the remaining vertices by one, ensuring that the original center(s) remain the center(s) of the resulting smaller tree.

[!note] Every tree has either one center or two adjacent centres

---card--- ^fsrs-4ola93

Define Binary Trees

A binary tree is fundamentally a specialized type of rooted tree.

For trees having three or more vertices, the definition is based on vertex degrees:

1. Exactly one vertex has a degree of two; this vertex is designated as the root.
2. All other vertices must have a degree of either one or three.

A binary tree is also referred to as a 2-ary tree.

Key Properties

• Vertex Count: The total number of vertices ($n$) in a binary tree is always odd.
• Degree Three Vertices: If $p$ is the number of pendant vertices (leaves), the number of vertices with a degree of three is equal to $n - p - 1$.

---card--- ^fsrs-k496rx

Full, Complete and Perfect Binary Trees

[!note] Full/Strict Binary Tree Every node has either 0 or 2 children

[!note] Complete Binary Tree All Levels are completely filled except possibly last level, last level filled from left to right

[!note] Perfect Binary Tree All internal nodes have 2 children

---card--- ^fsrs-dl84y2

The maximum number of nodes in a binary tree at level $i$ is $2^i$.

Proof by Induction

This property, often called Property 1, states that the maximum number of nodes in a binary tree at level $i$ is $2^i$.

1. Base Case (Level $i=0$) Level 0 is where the root is located. The maximum number of nodes at level $i=0$ is $1$. Since $2^0 = 1$, the statement holds true for the base case.

2. Inductive Hypothesis (Level $k$) Assume that the maximum number of nodes at some level $k$ is $2^k$.

3. Inductive Step (Level $k+1$) We must show that the maximum number of nodes at level $k+1$ is $2^{k+1}$.

• In a binary tree, every node at level $k$ can have a maximum of two children (descendants at level $k+1$).
• By the Inductive Hypothesis, there are at most $2^k$ nodes at level $k$.
• Therefore, the maximum number of nodes at level $k+1$ is $2 \times 2^k = 2^{k+1}$.

Since the base case is true, and the inductive step holds, the theorem is proven.

---card--- ^fsrs-esn1yp

The maximum number of nodes in a binary tree of height $h$ is $2^{h+1} - 1$.

Theorem

The maximum number of nodes in a binary tree of height $h$ is $2^{h+1} - 1$.

Proof

The proof relies on Property 1 (Maximum Nodes at Level $i$ is $2^i$).

1. Level Contribution: The maximum number of nodes at any level $i$ in a binary tree is $2^i$. This maximum is achieved in a perfect binary tree.
2. Summation: To find the total maximum number of nodes ($N_{\max}$) for a tree of height $h$, we sum the maximum number of nodes from the root (level 0) up to the height $h$: $$N_{\max} = \sum_{i=0}^{h} 2^i = 2^0 + 2^1 + 2^2 + \cdots + 2^h$$.
3. Result: This series is a geometric progression that sums directly to $2^{h+1} - 1$.

---card--- ^fsrs-voy3kp

For a binary tree with $n$ nodes, the minimum possible height ($h_{min}$) is $\lceil\log_2(n + 1)\rceil - 1$.

Proof of Minimum Height

The minimum height of a binary tree occurs when the tree is as balanced and full as possible, which means it contains the maximum number of nodes ($N_{\max}$) for a given height $h$.

1. We know that the maximum number of nodes for a tree of height $h$ is $N_{\max} = 2^{h+1} - 1$. Therefore, for a tree with $n$ nodes and height $h$: $$n \leq 2^{h+1} - 1$$
2. Rearrange the inequality to isolate $h$: $$n + 1 \leq 2^{h+1}$$
3. Take the base-2 logarithm of both sides: $$\log_2(n + 1) \leq h + 1$$
4. Isolate $h$: $$h \geq \log_2(n + 1) - 1$$
5. Since the height ($h$) must be an integer, the minimum possible height is obtained by taking the ceiling of this expression: $$h_{min} = \lceil\log_2(n + 1)\rceil - 1$$

---card--- ^fsrs-ka87k1

For a full binary tree with n nodes: $h_{\max} = (n-1)/2$

see note copy

---card--- ^fsrs-cdojah For a full binary tree with $n$ nodes, the number of leaf nodes ($L$) is given by the formula: $$L = \frac{n+1}{2}$$

See note copy