Compsci 120

Unordered choice with repetitions

Given n objects, we want to select r objects with replacements

Unordered choice without repetitions

Given n objects, we want to select r objects with replacements

Ordered choice without repetitions

Given n objects, we want to select r objects with replacements

Ordered choice with repetitions

Given n objects, we want to select r objects with replacements

n vertices, simple and connected graph with each vertex having degree 2.

Cn- cycle graph.

n vertices, simple graph without loops such that every unordered pair of distinct vertices is connected by an edge. Total edge count is n(n-1) / 2

Kn - Complete graph.

n vertices in one set and m vertices in the other set, is a simple graph without loops. This graph doesn’t contain any odd length cycles.

Kn,m - Bipartite graph.

Where there is a path between every pair of vertices.

Connected graph

A path where consecutive vertices are adjacent

Walk.

Adjacent.

Two vertices that are directly connected by an edge.

What G graph has these 3 properties of a tree.

1. G is connected and has no cycles.
2. There is a unique path between each two vertices in G.
3. G is connected and the number of edges in G is n - 1

Handshake lemma.

The sum of degrees is equal to 2 times the total number of edges.

A non-decimal number that is positive or negative number, including zero.

Integer.

In the form of p/q, which are both integers and the denominator is non-zero.

Rational number.

Positive integers

Natural number.

Real number.

The formula for a simple undirected graph with n vertices, the maximum number of edges is: