Graph Theory

Graph

A pair G = (V,E), where V is a nonempty finite set and E is a set of 2-elements subsets of V.

Adjacent

If u, v are in V, then u is adjacent to v provided {u, v}.

{u, v} is an edge of G, and u and v are its endpoints.

Degree

The degree of v is the number of edges that attach to v. d(v)

∑d(v) = 2|E|

The sum of all the degree numbers is 2x the number of edges in a graph.

Complete Graph

If all pairs of distinct vertices are adjacent in G, we call G complete.

Complement

G'. The graph with the same vertex set as G and the following edge set: if two vertices u and v are adjacent in G, then they are not adjacent in G'.

Handshaking Lemma

States 2 things.

1) The sum of all the degrees of all the vertices of a graph is equal to twice the number of edges.

2) An undirected graph has an even number of vertices of odd degree.

Induced Subgraph

These are formed by using only vertex deletion. Any edges that can be kept are kept.

Spanning Subgraph

These are formed by using only edge deletion. This has the same vertices as its super-graph.

Subgraph

G is a subgraph of H provided V(G) is a part of V(H) and E(G) is a part of E(H).

Clique

A subset of vertices in a graph where any two distinct vertices are adjacent.

Clique Number

The size of a largest clique in G.

Independent Set

A subset of vertices in a graph where no two vertices are adjacent.

If a graph has at least 6 vertices, then w(G) ≥ 3 or G' ≥ 3.

Theorem

Walk

A walk in G is a sequence of vertices with each vertex adjacent to the next. You can repeat vertices in a walk.

Path

A path is a walk in which no vertex is repeated. It travels from vertex to vertex along the edges of a graph.

The length of path is the number of edges it traverses, which is one less than the number of vertices in the path.

A path does not traverse any edge of a graph more than once.

Theorem

If there is a walk from (a,b), then there is a path from (a,b).

Important

Connected to

Let u,v be in V(G). u is connected to v provided that there is a (u,v) path in G.

A vertex can be connected to itself.

Theorem

The is-connected-to relation is an equivalence relation.

Theorem

A vertex cannot be adjacent to itself.

Theorem

Circuit

A path that begins and ends at the same node

Component

A component of G is a subgraph of G induced on an equivalence class of the is-connected-to relation on V(G). If we partition the vertices, two vertices are in the same part exactly when there is a path from one to the other.

Connected

An graph is connected provided each pair of vertices is connected by a path.

Cut vertex

A vertex v is a cut vertex if G-v has more components than G. If G is a connected graph, v disconnects it.

Cut edge

An edge e is a cut edge if G-e has more components than G. If G is a connected graph, e disconnects it.

If e is a cut edge of a CONNECTED graph G, then G-e has exactly 2 components.

Proof

Cycle

A cycle is a walk of length at least 3, in which the first and last vertex is the same, but no other vertex is repeated.

Forest

If G contains no cycles, G is a forest.

Tree

A tree is a connected, acyclic graph.

For any 2 vertices (x,y) in a tree, there is a unique (x,y)-path.

Proof

Every edge of a tree has a cut edge.

Proof

Leaves

A leaf of a graph is a vertex of degree 1.

Every tree with at least two vertices has a leaf.

Proof

Division Theory

a and b are integers with b > 0. There exist unique integers q and r such that a = qb + r and 0 < r < b:

Moreover, there is only one such pair of integers.

Greatest Common Divisor

Let a, b be integers. We call an integer d the greatest common divisor of a and b provided

(1) d is a common divisor of a and b and

(2) if e is a common divisor of a and b, then e d.

The greatest common divisor of a and b is denoted gcd(a,b).

Mod GCD Theorem

Let a and b be positive integers and let c = a mod b. Then

gcd(a,b) = gcd(b,c)

Smallest positive integers

Let a and b be integers, not both zero. The smallest positive integer of the form ax + by,

where x and y are integers, is gcd(a,b).

Relatively Prime

Let a and b be integers.We call a and b relatively prime provided gcd(a,b) = 1. In other words, integers are relatively prime provided the only divisors they have in common

are 1 and -1.

More relatively prime

Let a and b be integers. There exist integers x and y such that ax + by = 1 if and only if a

and b are relatively prime.

GCD thing

Let a and b be integers, not both zero. Let d = gcd(a, b). If e is a common divisor of a and b,

then e|d.

Rule about modular arithmetic.

Let a and b ∈ Zn. Then a ⊕ b ∈ Zn and a ⊗ b ∈ Zn.

Modular subtraction.

Let n be a positive integer, and let a, b ∈ Zn. Then there is one and only one x ∈ Zn such that

a = b ⊕ x.

Modular Reciprocals

Let n be a positive integer and let a ∈ Zn. If a has a reciprocal in Zn, then it has only one

reciprocal.

Lists with repetitions allowed

There are n^k ways to construct a k-list using an n-set.

Subset counting: The number of k-element subsets of an n-element set.

n choose k

Counting subsets of a set.

Let A be a finite set. The number of subsets of A is 2^|A|

|A|+|B| = |A∪B| + |A∩B|

Adding two sets.

The length of path is the number of edges it traverses, which is one less than the number of vertices in the path.

A path traverses k edges and k+1 vertices, always.

Suppose a, b, p ∈ Z and p is a prime. If p|ab, then p|a or p|b.

Number theory tool

Invertible Elements

Let n be a positive integer and let a ∈ Zn. Then a is invertible if and only if a and n are relatively prime.

Cut edges don't apply to cycles