Graph Theory Definitions and Concepts

End vertices

Two vertices v1 and v2 of edge e1 = (v1,v2)

Parallel Edges

Edges with the same end vertices

Loop

An edge connecting a vertex to itself (vk,vk)

Simple Graph

A graph without parallel edges or loops

Empty Graph

A graph with no edges

Null Graph

A graph with no vertices

Trivial Graph

A graph with only one vertex

Adjacent Edges

Edges with a common end vertex

Adjacent Vertices

Vertices connected by an edge

Degree of a vertex d(v) or deg(v)

(special case too)

Total number of edges that have that vertex as an end vertex (loops counted twice)

Pendant Vertex

A vertex with degree 1

Pendant Edge

An edge that is connected to a pendant vertex (vertex with degree 1)

Isolated vertex

Vertex with degree 0

Δ(G)

Max degree in graph

δ(G)

Min degree in graph

Theorem to find total # of edges from degrees

Let G = (V,E) be an undirected graph with m edges. Then 2m = ∑deg(V). Even if multiple edges and loops present.

Theorem (maximum degree)

With a simple graph with n vertices, the maximum degree is n-1, as there's n-1 vertices for any single vertex to connect to.

Theorem (δ(G) calculation)

δ(G) can be found by seeing how many max-degree vertices you have.

Subgraph of G

(V,E), is Gi: (Vi, Ei), if and only if Vi ⊆ V, Ei ⊆ E. Ie each edge in Gi has the same adjacent vertices as in G.

Complete Graph (Kn)

(also give degree sequence)

Denoted by Kn, n = # of vertices. A simple graph in which every vertex is adjacent to all other vertices. All possible edges included in the graph. Each vertex degree is n-1. Degree sequence: n-1, n-1, n-1,...,n-1 (n times).

Cycle graph (Cn)

(also give degree sequence)

Denoted by Cn, n = # of vertices, n >= 3. Graph with degree sequence 2 for all vertices. And only includes edges {(v1,v2), (v2,v3),...,(vn-1,vn), (vn,v1)}. Degree sequence: 2,2,2...,2 (n times).

Wheel graph (Wn)

(also give degree sequence)

Denoted by Wn, n = # of vertices excluding the extra vertex added. Add one vertex to the cycle graph Cn (n>=3). Connect that vertex to all other vertices. Degree sequence: n, (then) 3,3,...,3 (n times).

Complimentary graph (G̅)

Denoted by G̅. Same vertices as G. Consists only of all the possible edges that don't exist in G. G∪G̅ should be a complete graph. K̅n = empty graph with n vertices.

Bipartite Graph

A simple graph G: (V,E) where you can partition V into two disjoint sets V1, V2, such that V1∪V2 = V. And every edge connects a vertex in V1 to a vertex in V2. No two v1 vertices, and no two v2 vertices, can be adjacent by themselves.

Walk

Sequence of vertices and edges that helps us travel between two vertices in a graph

(Can repeat edges/vertices)

(Initial and terminal vertices can be the same)

Path

A walk with no repetition of vertices

(except for initial and terminal vertices)

Connected vertices

Two vertices are connected if there is a u•v walk between them (and vice versa)

Complete Bipartite Graph

(also give degree sequence)

Denoted by Km,n

With m vertices in set V1, and n vertices in set v2

Bipartite graph that contains every possible edge from v1 to v2 vertices and vice versa

Degrees in Complete Bipartite

With Km,n

For vertices in the v1 (m) set, the degree is n

For vertices in the v2 (n) set, the degree is m

How tell if graph is bipartite (coloring method)

1. Start at random vertex

2. Find adjacent vertex and assign a different color

3. Repeat step 2 alternating between the two colors until all vertices colored

If:

Every pair of adjacent vertices has a different color, it's bipartite

Else:

Not bipartite

Issue with coloring method

Slow time run

Initial Vertex

Starting vertex in a walk

Terminal vertex

Ending vertex in a walk

Trail

A walk with no repeated edges

(vertices can still repeat)

Theorem: Relationship between Path and Trails

Path implies Trail

If you want to repeat an edge, you need to return to a vertex you've been to already

Closed Walk

Walk from a vertex to itself

Circuit

Closed trail

Cycle

Closed path

Length of Walk

total # of edges you go over to get to terminal vertex

Circleless Graph

(and how to know if it's one)

Graph with no circuits

Any graph is circleless if:

-No loops

-At most one path to travel between any pair of vertices

Theorem: How to tell if graph is bipartite (cycle length)

A given simple graph is bipartite if and only if it does not have an odd-length cycle

For what values of N wiill Kn be bipartite?

Only n=2

-Any other n value > 2 can find an odd-length cycle (triangle)

-n=1 doesn't work because can not partition a single vertex into two sets

For what values of N wiill Cn be bipartite?

When n is even

n odd can't work b/c odd length cycle

Regular Graph / n-regular

Regular: Each vertex of graph has same degree

n-regular: Each vertex of graph has degree n

u•v walk

A walk starting at u and ending at v

Connected Graph

A graph where all vertices are connected (a walk exists between every pair of vertices)

(Trivial graph counts as connected)

Cut vertex

A single vertex in a connected graph whose removal increases the # of connected components in a graph

Cut edge

A single edge whose removal increases the # of connected components in the graph

Euler Walk

A walk that uses each edge exactly once

Euler circuit

Closed Euler walk

(closed walk that uses each edge exactly once)

Euler graph

A connected graph that has a Euler circuit

Theorem for Euler walk

A connected graph G has a Euler walk if and only if it has exactly 2 vertices with an odd degree

Theorem for Euler circuit

A connected graph has a Euler circuit if and only if all vertices in graph have an even degree

Hamiltonian Circuit

A circuit that uses every vertex in a graph exactly once

Hamiltonian Path

A path that uses every vertex in a graph exactly once

Hamiltonian Graph

A graph that contains a Hamiltonian circuit

Theorem relating Hamiltonian circuits and Hamiltonian paths

If a graph has a Hamiltonian circuit, it also has a Hamiltonian path

(but not vice versa)

Dirac's Theorem

If:

- G is a simple graph with n vertices with n>=3, such that the degree of every vertex in G is at least n/2

Then:

- G has Hamiltonian circuit

(If not, still possible to have Hamiltonian circuit)

Ore's Theorem

If:

- G is a simple graph with n vertices with n>=3 such that d(u)+d(v) >= n for every pair of nonadjacent vertices u and v in G

Then:

- G has a Hamiltonian circuit

(If not, still possible to have Hamiltonian circuit)