Discrete Math: Combinatorics & Graph Theory

What is the Multiplication Rule (Fundamental Counting Principle) in combinatorics?

If a task can be performed in n ways and a second task can be performed in m ways independently, then there are n * m ways to perform both tasks.

Define the degree of a vertex in an undirected graph.

The degree of a vertex is the number of edges incident to it, with self-loops typically counted twice.

What is the formula for the number of r-permutations of a set with n distinct elements?

P(n, r) = n! / (n - r)!

In graph theory, what are the two defining characteristics of a 'tree'?

A tree is an undirected graph that is both connected and contains no simple cycles (acyclic).

In a complete graph Kn, what is the degree of every vertex?

Every vertex in a complete graph with n vertices has a degree of n - 1.

What is the formula for the number of r-combinations of a set with n elements?

C(n, r) = n! / (r! * (n - r)!)

State the Principle of Inclusion-Exclusion for the union of two finite sets A and B.

The size of the union is given by |A ∪ B| = |A| + |B| - |A ∩ B|.

State the Handshaking Lemma regarding the sum of degrees in a graph G = (V, E).

The sum of the degrees of all vertices in the graph is equal to twice the number of edges: Σ deg(v) = 2|E|.

What is the necessary and sufficient condition for a connected undirected graph to contain an Euler circuit?

A connected undirected graph has an Euler circuit if and only if every vertex has an even degree.

Define a bipartite graph.

A bipartite graph is a graph whose vertices can be partitioned into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other.