Graph Theory Midterm 1

Graph

Pair of sets where one set consists of vertices and the other set consists of edges connecting those vertices.

Order (|G|)

The number of verticies

||G||

The number of edges

Subgraph of G

A graph G ‘ = (V’, E’) where V’ ⊆ V and E’ ⊆ E

Induced Subgraph of G

It contains all edges xy ∈ E if x,y ∈ V

Complete Graph Kⁿ

A complete graph on n vertices

Independent set of edges

A set of edges that do not share any endpoints

Independent set of vertices

A set of verticies that are not adjacent

d(G)

Average degree of vertices in G

δ(G)

Minimum degree of a vertex in G

Δ(G)

The maximum degree of a vertex in G

ε(G)

|E|/|V|

Proposition 1.2.1

The number of vertices of odd degree in a graph is always even

Edge Cardinality Relation to Degree and Vertex Count

|E| = (1/2)d(G)*|V|

ε(G) relation to d(G)

ε(G) = (1/2)d(G)

Proposition 1.2.2

Every graph G with at least one edge has a subgraph H with δ(G) > ε(H) ≥ ε(G)

In Class Lemma Chap 1

Let G = (V,E) be a graph, and let w be a vertex such that d(w) ≤ ε(G). Then H = G - {w} has ε(H) ≥ ε(G)

Girth g(G)

The minimum length of a cycle in G (infinity if no cycles)

Cicumference

The maximum length of a cycle in G (0 if no cycles)

Diameter

Greatest distance between any two vertices in G

Prop 1.3.1

Every graph G contains a path of length δ(G) and a cycle of length at least δ(G) + 1. (If δ > 1)

Proposition 1.3.2

Every graph G containing a cycle satisfies g(G) ≤ 2diam(G) + 1

Proposition 1.3.3

A graph G of radius at most k and Δ(G) ≥ 3 has fewer than (d/(d-2))(d-1)^k vertices

Proposition 1.4.1

The vertices of a connected graph G can always be enumerated so that it is connected for every i.

Minimally connected

Removing any edge makes it disconnected

Maximally acyclic

T contains no cycle but T + xy does, if x and y are non-adjacent

Corollary 1.5.2

Vertices of a tree can always be enumerated so that the last vertex in the list has a unique neighbor in the list without it

Corollary 1.5.3

A connected graph with n vertices is a tree if and only if it has n - 1 edges

Corollary 1.5.4

If T is a tree and G is any graph with δ(G) ≥ |T| - 1, then T⊆G.

Spanning Tree of G

T is a spanning tree if T is a tree with |G| vertices or is a maximally acyclic subgraph or is a minimally connected subgraph that covers every vertex

Algorithm for spanning tree

While T contains a cycle, remove an edge in that cycle, until no cycles

Minimum Spanning Tree

A spanning tree that minimizes total edge weight

Prim Algorithm

Start with only one vertex. Then add the cheapest edge that has one vertex in your set of vertices and one vertex outside of it.

Kruskal

Start with all vertices and no edges. Then, add the cheapest edge that doesn’t make a cycle.

Reverse Delete

Start with G. Remove the edge with the largest weight, if the graph still remains connected. Do this til you get T.

Cut Lemma

Pick a subset of vertices that is not V. Then, the minimum cost edge with one end in S and one end in V - S is in every minimum spanning tree.

Cycle Lemma

If there exists a cycle in G, the most expensive edge in this cycle does not belong to any minimum spanning tree of G.

Depth first search

Go as deep as possible. When you hit a dead-end, go back until you are at a vertex with an unexplored neighbor, and go from there.

1.6.1

G is bipartite iff G has no odd cycles

Euler Tour

A walk on a graph that traverses every edge exactly once.

Matching

If every vertex in the desired subset of the vertices is incident with an edge in the matching.

Perfect Matching

Every vertex is matched

Vertex cover

A set of vertices that is incident to every edge in the graph

Edge cover

A set of edges that is incident with every vertex

Alternating path

A path that starts with an unmatched vertex in A, and then alternates between edges in and edges not in the Matching.

Augmenting path

An alternating path that ends in an unmatched vertex in B

2.1.1

The maximum cardinality of a matching in G is equal to the minimum cardinality of a vertex cover of its edges.