MATH 232 Discrete Math 2 Final

Degree-Sum Formula

Degrees of all vertices will be equal to 2 * number of edges

Bipartite graphs

A graph is called bipartite if its vertex can be partitioned into disjoint subsets v1 and v2 such that ever edge in the graph joins the vertex in v1 in v2.

K-coloring

A way of coloring the vertices using at most k colors so that no adjacent vertices have the same color. A graph has such a k-coloring is called k-colorable.

Isomorphism

f: G -> H is a bijective function from the vertex set of G to the vertex set of H such that vertices u,v in G are adjacent if and only if f(u), f(v) are adjacent in H and if the inverse function f^-1 is also a homomorphism

Complete bipartite graph k(m,n)

has a biprartition (v1, v2) with |v1| \= m and |v2| \= n and ever possible edge between a vertex v1 and v2

Graph Homomorphisms

Let G \= (V, E, P) and H \= (v2, E2, P2) be 2 graphs. A graph homomorphism from G to H is a function homomorphism from G to H is a function f: v1 -\> v2 with the property that if u1, u2 are adjacent vertices in G, then f(v1) and f(v2) are adjacent in H

Subgraph

A graph G’ is a subgraph of G if the vertex and edge sets of G’ are subsets of G

Walk

of length n in G is a sequence of vertices in v0, v1, ..., vn in G such athat vi is always adjacent to vi+1

Path

a walk without repeated vertices. every path is a trail

Trail

a walk without repeated edges. every path is a trail

Circut

is a non-empty trail which begins and ends at the same vertex

Cycle

is a special kind of circut in which only the first and last vertices are equal

Connected

A graph G is connected if for every pair of distinct vertices v1 and v2 in G, there exists a walk beginning at v1 and ending at v2

Connected Components

maximal connected subgraphs

Vertex cut

Let G = (V, E, P) be a non-complete graph. A Subset V' ⊆ V is a vertex cut if G - V' is disconnected

edge connectivity, λ(G)

The minumum number of edges that must be removed to disconnect the graph (edge cut) or 0 if |v| = 1

Vertex connectivity, k(G)

the minimum number of vertices which must be removed to either disconnect the graph or produced a graph with one vertex

Theorem with edge connectivity and vertex connectivity

For any graph G k(G)

Euler's Formula

Let G be a connected planar graph with v vertices and e edges. The number of regions in any planar representation of G is r \= e - v + 2

Planar graph

a graph is planar if it can be drawn in the plane without any edges crossing

Degree of region

Degree of a region in a planar representation is the length of its boundary

Corollary 1

A connected planar graph with v \=\> 3 vertices and e edges will have e

Corollary 1.5

A connected planar graph with v \>\= 3 vertices, e edges, and no 3-cycles has e

Corollary 2

If G is a connected planar graph, then G always has vertex degree of 5 or less

Contracting

contracting an edge produces a new graph G/e1 where e is removed and its endpoints have been merged

Subdividing

Inserting a vertex into the middle of an existing edge

Homeomorphic graphs

Graphs G and H are called homeomorphic if one can be obtained form the other by a sequence of subdivisions and smoothings

Kwatowski's Theorem

a graph is nonplanar if and only if it contains a subgraph homeomorphic ot K3,3 or k5

Chromatic Number X(G)

If G is some graph is the smallest integer k for which G is k-colorable

Four Color Theorem

If G is a planar graph, X(G)

Chromatic Polynomial

The number of ways to k-color G

G is an edgeless graph: P(G, K) \= k^n

Fundamental Reduction Theorem

Let e be any edge in graph G. P(G, k) \= P(G-e, k) - P(G/e, k)

Chromaticlly Equivalent

Two graphs G and H are chromatically equivalent if P(G,k) = P(H, k)

Induced subgraph

Let G \= (V, E, P) and let w ⊆ V. The induced subgraph on w has vertex set w and every edge in E that joins 2 vertices of w

Clique

A set of vertices in a graph whose induced subgraph is complete

Independent set

A set of vertices in a graph whose induced subgraph is edgeless

Ramsey's Theorem

For any positive integers m and n, there esists a least positive integer R(m,n) suchc that every graph on R(m, n) vertices contains an m-clique or an n-independent set.
R(2, n) \= n
R(m,n) \= R(m,n) because every clique in G is an independent set in the completment of G and vice verse
R(m, 1) \= 1
R(2, 3)