Graph Theory Flashcards
Define a graph
An ordered pair (V, E), where V is a non-empty finite set and E is an unordered subset of 2 elements of V.
Define isomorphic graphs
Two graphs, G and H are isomorphic if there exists a bijection φ: V(G) → V(H) such that xy ∈ E(G) if and only if φ(x)φ(y) ∈ E(H).
Define a subgraph
H is a subgraph of G if H is a graph with V(H) ⊆ V(G) and E(H) ⊆ E(G).
Define a complete graph
The graph with all possible edges included.
Define an empty graph
The graph with vertices and no edges.
Define a path graph
The graph with V = {v0, v1, …, vn} and E = {v0v1, v1v2, …, v(n-1)vn}.
Define a cycle graph
The graph with V = {v0, v1, …, vn} and E = {v0v1, v1v2, …, v(n-1)vn, vnv0}.
Define adjacent vertices
Given a graph G, two vertices, v and w are adjacent if vw ∈ E(G).
Define a walk
Given a graph G, a walk is a sequence v0v1…vt of (not necessarily distinct) vertices of G such that v(i-1)vi ∈ E(G) for all 1 ≤ i ≤ t.
Define a closed walk
A closed walk is a walk with the same first and last vertices.
Define a path
A path is a walk with distinct vertices.
Define connected vertices
Vertices x, y in G are connected if there exists a path between them.
Define a connected graph
G is connected if every pair of points in G is connected.
Define a component of a graph
H is a component of a graph G if it is a connected subgraph of G.
Define an acyclic graph
A graph G is acyclic if it does not have any subgraphs which are cycles.
Define a tree
A tree is a connected acyclic graph.
Define a minimal connected graph
A graph G is minimal connected if it is connected, but removing any edge e from E(G) results in G – e not being connected.
