- Graph, Vertices, Edges, Endpoints
- Join, Neighbor
- The Open Neighborhood of a vertex v in a graph G, denoted N(v), is the set of all neighbors of v.
- The Closed Neighborhood of a vertex v in a graph G, denoted N[v], is the set of all neighbors of v and itself.
- Proper Edge: joins two distinct vertices.
- Self-loop: joins a single endpoint to itself.
- Multi-edge: A collection of tow or more egdes having identical endpoints.
- Edge Multiplicity: the number of egdes within the multi-edge.
- Simple Graph: no self-loops, no multi-edges.
- Loopless Graph: no self-loops.
- Null Graph: no vertix, no edge.
- Trivial Graph: 1 vertex, no egde.
- Directed Egde, Arc ...
- Underlying Graph: delete all edge directions.
- Formal Specification of a Simple Graph: given by a Adjacency Table
- Formal Specification of a General Graph: given by a Incidence Table
- Formal Specification of a General Digraph: given by a Incidence Table, with head and tail designated.
- Adjecent Vertices, Adjecent Edges, Incidence, Degree, Valence, D-valent Vertex
- Degree Sequence: the sequence formed by arranging the vertex degrees in non-increasing order.
- Graphic: permutation of a degree seqeunce of a simple graph, realized by such a simple graph.
- Indegree, Outdegree
A non-trivial simple graph G must have at least one pair of vertices whose degrees are equal.
Proof: Pigeonhole Principle
The sum of vertex degrees = number of egdes x 2
In a graph, there is an even number of vertices having odd degree.
Sum of Degree Sequence is even.
Forall sequence of natual numbers whose sum is even, there exists a graph of the same degree sequence.
let <d₀, d₁, ... dₙ> be a graphc sequence, d₀ = m, the vertex of the graph that realize it, that correspondes to d₀, is adjacent to the next m vertices.
<d₀, d₁, ... dₙ> is graphic, d₀ = m ⇒ <d₁ - 1, ... ,dₘ₋₁ - 1, dₘ ... dₙ> is graphic
Proof: by induction on the vertex-set.
In a digraph, sum of indegrees = sum of outdegrees = number of edges
- Regular Graphs: all vertices have common degree k, denoted k-regular.
- Complete Graph: denoted Kₙ
- Bipartite Graph: denoted Kₘₙ
- Bouquet: denoted Bₙ
- Dipole: denoted Dₙ
- Path Graph: denoted Pₙ
- Cycle Graph: denoted Cₙ
- Hypercube: denoted Qₙ
- Circular Ladder Graph: denoted CLₙ
- Circulant Graph: denoted circ(n : S)
- Intersection Graph: for a simple graph G with vertex-set VG={v1, v2, …, vn}, there exists a family of sets F={S1, S2, …, Sn} such that vertex vi is adjacent to vj if and only if i ≠ j and Si ∩ Sj ≠ ∅.
- Interval Graph: an intersection graph corresponding to a family of intervals on the real line.
- Line Graph: denoted L(G), swap the vertex-set and the edge-set of a graph G, while maintaines the adjacencies.
- Walk: an alternating sequance of vertices and egdes, blah blah blah...
- Directed Walk: follows head and tail.
- Length of a walk: the number of edge-steps in the walk sequence.
- Close Walk: is a nontrivial walk that begins and ends at the same vertex.
- Open Walk: is a nontrivial walk that begins and ends at defferent vertex.
- Concatenation: Duh.
- Distance: denoted d(s, t), the length of the shortest s-t walk if one exists, ∞ otherwise.
- Eccentricity: denoted ecc(v), the farthest distance of all walks from v.
- Diameter: denoted diam(G), the maximum of all eccentricities in G.
- Radius: denoted rad(G), the minimum of all eccentricities in G.
- Central Vertex: forall vertex v in graph G, ecc(v) = rad(G)
- Reachable from, Connected
- Mutually Reachable
- Strongly connected: every vertex is reachable from every other vertex.
- Strongly Orientable, Strong orientation
- Trail: a walk in which all edges are distinct.
- Path: a open walk in which all vertices (and thus edges) are all distinct.
- Reduction of Walk W by Subwalk W': W - W', given W a walk and W' a closed subwalk in W, thus obtained by deleting all vertices in W' expect for the vertices they intersects.
- Reduced Walk: obtained by multiple walk reduction.
- Cycle: a closed walk in which all vertices (and thus edges) are all distinct.
- Acyclic Graph
- Hamiltonian Cycle: A cycle that visits each vertex of a Hamiltonian Graph exactly once.
- Decomposition: A collection of edge-disjoint cycles, C1, C2, …, Cm, is called a decomposition of a closed trail T if each cycle Ci is either a subwalk or a reduced walk of T and the edge-sets of the cycles partition the edge-set of trail T
- Eulerian Trail: a path that passes all egdes exactly once.
- Eulerian Tour: a closed Eulerian Trail.
- Eulerian Graph
- Girth: the length of the shortest cycle, defined to be ∞ if there's no cycle in a graph.
- Tree: a connected graph with no cycle.
Every open x-y walk W is either an x-y path or contains a closed subwalk
Let W be an open x-y walk. Then either W is an x-y path or there is an x-y path that is reduced walk of W.
The distance from a vertex x to a a reachable vertex y is always realizable by an x-y walk.
A graph G is bipartite <=> it has no cycles of odd length
Every non-trivial, closed trail T contains a subwalk that is a cycle
A closed trail can be decomposed into edge-disjoint cycles
Proof by induction on the closed trail, along with Proposition 1.5.5