Discrete Mathematics - Graph Theory & Combinatorics Flashcards

Question 1

Generalized Pigeonhole Principle

Accepted Answer

If $N$ objects are placed into $k$ boxes, then at least one box contains at least $\lceil N/k \rceil$ objects.

Question 2

Binomial Coefficient Formula

Accepted Answer

Counts the number of ways to choose $k$ elements from an $n$-element set without regard to order:
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

Question 3

Pascal's Identity

Accepted Answer

A foundational relation for binomial coefficients:
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ for $1 \le k \le n$.

Question 4

Permutation Formula

Accepted Answer

Counts the number of ordered arrangements of $k$ distinct elements chosen from $n$ available elements:
$$P(n, k) = \frac{n!}{(n-k)!}$$

Question 5

Handshaking Lemma

Accepted Answer

In any undirected graph $G = (V, E)$, the sum of the degrees of all vertices is equal to twice the number of edges:
$$\sum_{v \in V} \deg(v) = 2|E|$$

Question 6

Corollary of the Handshaking Lemma

Accepted Answer

Every undirected graph has an **even number** of vertices of odd degree.

Question 7

Eulerian Path vs. Eulerian Circuit

Accepted Answer

- **Eulerian Path**: A trail in a finite graph that visits every edge exactly once. Requires a connected graph with **exactly 0 or 2** vertices of odd degree.
- **Eulerian Circuit**: An Eulerian path that starts and ends at the same vertex. Requires a connected graph where **all** vertices have even degree.

Question 8

Hamiltonian Path vs. Hamiltonian Circuit

Accepted Answer

- **Hamiltonian Path**: A path that visits every *vertex* in the graph exactly once.
- **Hamiltonian Circuit**: A closed loop that visits every *vertex* exactly once and returns to the starting vertex. (Determining existence is NP-complete).

Question 9

Characterization of Bipartite Graphs

Accepted Answer

A graph $G$ is **bipartite** if its vertices can be partitioned into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$. Equivalent condition: A graph is bipartite if and only if it contains **no odd cycles**.

Question 10

Euler's Formula for Planar Graphs

Accepted Answer

For any connected planar graph drawn in the plane without intersecting edges, the number of vertices ($V$), edges ($E$), and faces ($F$, including the unbounded outer face) satisfies:
$$V - E + F = 2$$

Question 11

Planar Graph Edge Bound

Accepted Answer

For a simple connected planar graph with $V \ge 3$ vertices and $E$ edges:
$$E \le 3V - 6$$
If the graph contains no triangles ($C_3$), then $E \le 2V - 4$.

Question 12

Fundamental Properties of Trees

Accepted Answer

An undirected graph with $n$ vertices is a **tree** if and only if it satisfies any two of the following conditions:
1. It is connected.
2. It is acyclic (contains no cycles).
3. It has exactly $n - 1$ edges.

Question 13

De Morgan's Laws

Accepted Answer

- **Logic**: $
eg(P \land Q) \equiv 
eg P \lor 
eg Q$ and $
eg(P \lor Q) \equiv 
eg P \land 
eg Q$.
- **Set Theory**: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Question 14

Principle of Inclusion-Exclusion (PIE)

Accepted Answer

Calculates the cardinality of the union of multiple sets. For two sets:
$$|A \cup B| = |A| + |B| - |A \cap B|$$
For three sets:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Question 15

Power Set Cardinality

Accepted Answer

The power set $\mathcal{P}(S)$ is the set of all subsets of $S$. If $|S| = n$, then the cardinality of the power set is:
$$|\mathcal{P}(S)| = 2^n$$

Question 16

Chromatic Number $\chi(G)$

Accepted Answer

The minimum number of colors needed to color the vertices of a graph $G$ such that no two adjacent vertices share the same color. 
- For a complete graph: $\chi(K_n) = n$
- For any non-empty bipartite graph: $\chi(G) = 2$

Question 17

Spanning Tree Definition

Accepted Answer

A subgraph of a connected, undirected graph $G$ that includes all of $G$'s vertices and is a tree. A graph with $V$ vertices has a spanning tree with exactly $V - 1$ edges.

Question 18

Modus Ponens

Accepted Answer

A valid rule of inference stating that if $P$ is true and the conditional statement $P \implies Q$ is true, then $Q$ must be true. Symbolically: $((P \implies Q) \land P) \implies Q$.

Question 19

Modus Tollens

Accepted Answer

A valid rule of inference stating that if $P \implies Q$ is true and $Q$ is false ($¬Q$), then $P$ must be false ($¬P$). Symbolically: $((P \implies Q) \land 
eg Q) \implies 
eg P$.

Question 20

Steps of Mathematical Induction

Accepted Answer

1. **Base Case**: Show $P(n_0)$ is true for the initial value $n_0$.
2. **Inductive Hypothesis**: Assume $P(k)$ is true for an arbitrary integer $k \ge n_0$.
3. **Inductive Step**: Prove that $P(k) \implies P(k+1)$ is true, concluding $P(n)$ holds for all $n \ge n_0$.

Discrete Mathematics - Graph Theory & Combinatorics

Cards in this deck

Related Flashcard Sets

MONASH MTH2010 - Multivariable Calculus & Vector Calculus

SYDNEY CHEM1111 - Chemical Bonding, Thermochemistry & Chemical Equilibrium

GCP Associate Cloud Engineer - Cloud IAM, Compute Engine & Networking

JLPT N4 - Intermediate Japanese Grammar, Particles & High-Frequency Kanji