Graph Theory

D2 Graph Theory Rules

End vertices

2 vertices v1 and v2 that are connected to an edge

Parallel

Edges with same end vertices

Loop

An edge that connects a vertex to itself

Simple Graph

Graph with no parallel edges or loops

Empty Graph

Graph with no edges

Null Graph

Graph with no edges or vertices

Trivial Graph

Graph with one vertex

Adjacent Edges

Share a common vertex

Adjacent Vertices

Connected/shared by an edge

Degree of Vertex

d(V) = # of edges with V as ending vertex & loop is counted twice

Pendant Vertex

Vertex with degree 1

Pendant Edge

Graph with pendant vertex

Isolated Vertex

Vertex with degree 0

Handshaking Theorem

2m = ∑(vi∈V) deg(vi) where m is the # of edges

Degree Sequence

Sequences of degrees for each vertex from largest to smallest

Graphic

Degree Sequence of Simple Graph

Complete Graph

Kn where n is # of vertices; all vertices have degree of (n-1)

Cycle Graph

Cn where n is # of vertices; all vertices have degree of 2

Wheel Graph

Wn where n is # of vertices + 1; Cycle Graph but with a vertex in the middle that connects to all other vertices; all vertices have degree of n

Complementary Graph

Has same vertices as original but they are not adjacent

Bipartite Graph

Simple graph labeled as Rm,n if its vertex set V can be partitioned into 2 disjoint sets v1 and v2

Walk

finite sequences of edges and vertices that starts with initial vertex and ends on terminal vertex

Trail

walk with no repeated edges

Path

walk with no repeated vertices except for the initial and terminal vertices

Circuit

closed walk

Cycle

closed path

Cycle Graphs have bipartite version if _____

It has n=2k vertices

Complete Graphs have bipartite version if ______

It has ONLY 1 or 2 vertices

u-v walk

walk starting at u and ending at v

Connected

If u-v walk in graph exists

Cut Vertex

vertex of connected graph whose removal increases # connected components in graph

Cut Edge

edge of connected graph whose removal increases # connected components in graph

Euler Walk

walk that uses every edge exactly once

Euler Circuit

circuit that uses every edge exactly once

Connected Graph is Euler Graph if _____

It has Euler Circuit

Connected Graph has Euler Circuit if ______

Every vertex has even degree

Connected Graph has Euler Walk if _____

Exactly 2 vertices have odd degree

Hamilton Circuit

circuit that uses every vertex exactly once

Hamilton Path

path that uses every vertex exactly once

Graph with Hamilton Circuit is _____

Hamilton Graph

G (simple graph with n≥3 vertices) has Hamilton Circuit if ____

d(v) + d(w) ≥ n where v & w aren’t adjacent or if every vertex has degree ≥ n/2

G (simple graph with n vertices) has Hamilton Path if _____

d(v) + d(w) > n-1 where v & w aren’t adjacent