Graph Theory Exam 1

graph isomorphism

function f between G and H such that f is a bijection and {u,v} in E(G) ←→ {f(u), f(v)} in E(H)

degree

the number of edges incident to a vertex, counting loops twice

degree sequence

degrees of all vertices of a graph written in increasing order

adjacent

describes vertices that are connected by an edge

incident

describes an edge’s relationship to its endpoints

Handshake Lemma

For any graph G, the sum of the degrees of all vertices is equal to 2 times the number of edges

subgraph

V(H) is a subset of V(G) and E(H) is a subset of E(G)

subgraph induced by S

For S a subset of V(G), G[S] with V(G[S]) = S

Contraction (G/e)

remove an edge, then merge its endpoints and take all incident edges with it to be incident with new single vertex

complete graph (Kₙ)

a graph with n vertices and all possible edges

regular graph

a graph in which all vertices have the same degree

bipartite graph

a graph in which V(G) is a union of A and B with no overlap, and every edge is between a vertex in A and a vertex in B

cube (Qₙ)

a graph with vertices denoted by length n binary strings and edges connecting vertices that differ in exactly one spot

walk

finite sequence of edges

trail

walk with distinct edges

path

walk with distinct vertices

G is bipartite

all cycles have even length if and only if…

spanning tree

a subgraph T of G s.t. T is a tree and V(T)=V(G)

disconnecting set

a set of edges F in G s.t. G-F is disconncted

cut set

a minimal disconnecting set

edge connectivity (λ(G))

the smallest size of a cut set

k-connected

removing any k-1 edges leaves G connected

bridge

one-element cut set

separating set

a set of vertices S in G s.t. G-S is disconnected

cut vertex

a size 1 separating set

vertex connectivity (κ(G))

the smallest size of a separating set

Eulerian trail

a closed trail that contains every edge of G

Eulerian graph

a graph that contains an Eulerian trail

semi-Eulerian graph

a graph that contains a trail that visits every edge (not necessarily closed)

G is Eulerian

All vertices have even degrees if and only if…

G is semi-Eulerian

A graph has 2 vertices of odd degree with the rest even degree if and only if…

cycle rank

the number of edges that have to be removed from G to get a spanning tree

fundamental cycle

a unique cycle in a spanning tree T that is obtained by adding an edge of G back