Combo vocab/theorems

graph

two finite sets, V (a set of vertices) and E (a set of pairs of unordered vertices/edges)

vertex

node

edge

pair of unordered vertices

order

size/cardinality of a graph’s vertex set

adjacent (vertices u,v)

uv ∈ E(G)

nonadjacent

uv ∉ E(G)

incident

e ∈ E contains vertex v

degree (deg(v))

number of edges incident with v

maximum degree (and its notation, ∆(G))

max degree of all vertex degrees in the graph

minimum degree (and its notation, δ(G))

min degree of all vertex degrees in the graph

degree sequence

the sequence of the vertex degrees, usually listed in descending order

walk

a sequence of vertices v1, …, vk s.t. (vi vi+1) ∈ E ∀ i ∈ {1, …, k-1}

path

a walk in which all vertices are distinct

trail

a walk in which all edges are distinct

circuit/closed trail

a trail that begins and ends at the same vertex

cycle/closed path

a v1-vk path (k≥3) together with edge (vk,v1)

length (of a walk, path, trail, cycle, or circuit)

the number of edges

vertex deletion (and its notation, G \ v)

graph obtained by removing v and all edges incident to v from G

edge deletion (and its notation, G \ e)

graph obtained by removing e

connected

every pair of vertices can be joined by a path

connected component

each connected piece of a graph

cut vertex

a vertex whose removal causes the number of connected components to increase

cut set

proper subset of V(G) s.t. G-S is not connected

bridge

an edge whose removal causes the number of connected components to increase

complement (and its notation, Gbar)

the graph whose vertex set is the same as G, but whose edge set is all edges not in G

regular and r-regular

if every vertex has the same degree (deg(v)=r)

subgraph (H subgraph of G)

V(H) ⊆ V(G) and E(H) ⊆ E(G)

induced subgraph , S subset of V(G)

the subgraph with vertex set S with all edges between vertices in S

bipartite

its vertex set can be partitioned into two sets X and Y so that every edge has one vertex in X and one in Y

partite sets

the two sets of a bipartite graph

isomorphic

there exists a mapping from one vertex set to another that preserves adjacencies

distance d(u,v)

the number of edges of the shortest u-v path

adjacency matrix

the nxn matrix A whose (i,j) entry is 1 if (vi,vj) ∈ G, 0 otherwise

distance matrix

the nxn matrix D whose (i,j) entry is d(vi,vj)

tree

a connected graph that contains no cycles

forest

a collection of one or more trees

leaf

a vertex of degree 1 in a tree

spanning tree

Tree that contains every vertex of G

weighted graph

a graph G together with a weight function

minimum weight spanning tree

the sum of the weights of the edges of T is no more than the sum for any other spanning tree

Eulerian trail

a trail in G that contains every edge of G

Eulerian circuit

a circuit in G that contains every edge of G

Eulerian graph

a graph that contains an Eulerian circuit

Hamiltonian path

a path that visits all vertices of G

Hamiltonian cycle

a cycle that visits all vertices of G

Hamiltonian graph

a graph that contains a Hamiltonian cycle

S-free (for a set S, a collection of graphs)

G does not contain any of the paths in S as induced subgraphs

H-free (for a graph G)

G does not contain a copy of H as an induced subgraph

planar

a graph that can be drawn in a way that pairs of edges intersect only at vertices or not at all

nonplanar

a graph that cannot be drawn in a way that pairs of edges intersect only at vertices or not at all

planar representation

a drawing of a graph drawn in a way that pairs of edges intersect only at vertices or not at all

region

enclosed area of a planar representation of graph G

exterior region

the region on the outside of a planar representation of G

k-coloring

a function K: V(G)→[k]

proper k-coloring

no 2 adjacent vertices in G have the same color

k-colorable

a proper k-coloring of G exists

chromatic number (and its notation, χ(G))

the smallest integer k s.t. G is k-colorable

Kn

complete graph of order n, every vertex is connected to every other vertex

En

graph of order n with no edges

Cn

the graph of a cycle on n vertices

Pn

the graph of the path on n vertices

Kn,m

complete bipartite graph with sets of size n and m

Kruskal's Algorithm

add edges of minimum weight that don't form a cycle until MST is formed

Hierholzer’s Algorithm is used for

identifying an Eulerian circuit in Eulerian graph

Prufer sequences are used for

providing a unique sequence representation of a labeled tree

Sum of degrees is equal to

twice the number of edges

every u-v walk contains

a u-v path

A graph with at least 2 vertices is bipartite iff

the graph contains no odd cycles

T is a tree of order n, T contains

n-1 edges

F is a forest of order n containing k connected components, F contains

n-k edges

A graph of order n is a tree iff

it is connected and contains n-1 edges

T is a tree of order n>=2

T has at least 2 leaves

Kruskal's algorithm produces

a minimum spanning tree

G is Eulerian iff

Every vertex has even degree iff the edges of G can be partitioned into edge-disjoint cycles

connected graph G contains an Eulerian trail iff

there are at most two vertices of odd degree

connected graph G of order n, q edges, r regions

n-q+r=2

K_3,3

is nonplanar

K_5

is nonplanar

every planar graph is

4-colorable

factorial (n!)

n(n-1)(n-2)…(2)(1)

permutation

an ordering of n objects (n!)

falling factorial power (x^k_)

x(x-1)…(x-k+1)

rising factorial power (x¯k)

x(x+1)…(x+k-1)

binomial coefficients

(n k)

algebraic proof

transforming one side of an equation to the expression on the other side using substitutions and arithmetic operations

combinatorial proof

showing both sides of an equation count the same thing (counting in 2 ways)

multinomial coefficient (k1+…+km = n)

(n k1,k2,…,km)

multiset

allows for multiple instances of each element

the pigeonhole principle (if more than n objects are distributed among n containers, then)

some container has more than one object

floor

largest integer m satisfying m ≤ x

ceiling

smallest integer m satisfying x ≤ m

relatively prime

two positive integers whose greatest common divisor is 1

generating function

∑k≥0 (ak*x^k) for a sequence {ak}

coefficient operator [x^k]

extracts the coefficient of x^k in a formal power series of x

partial fractions

N(x) / (ax+b)(cx+d) = A / (ax+b) + B / (cx+d)

recurrence relation

an expression for an in terms of n and values a0, a1, …, an-1

order of a recurrence relation (order k)

formula for an depends on only the previous k terms, requires k initial values

closed form of a recurrence relation

requires finitely many steps to complete and makes no reference to values of the sequence, except possibly the initial values

S1, …, Sm are finite sets with orders n1, …, nm, ways to select one from any set is?

n1+n2+…+nm

S1, …, Sm are finite sets with orders n1, …, nm, ways to select one from each set is?

n1 x n2 x…x nm