Math 61 - Graph Vocabulary

Graph

Denoted by letter G; a set of vertices of V(G) and edges E(G) ⊆ {(u, v) | u, v ∈ V}

Incident

When an edge e ∈ E(G) is denoted by (u, v). In this case, u and v are called adjacent vertices.

Loop

An edge denoted by (u, u)

Parallel

Multiple loops between {u, v} ⊆ V

Isolated

If u ∈ V is not adjacent to any w ∈ V, we say that v is isolated

Simple Graph

Graph G has no loops or parallel edges

Complete Graph

Denoted by Kn, where n is the number of vertices. This is a simple graph where |V(Kn)| = n, and there is an edge between each pair of vertices

Bipartite Graph

Graph composed of 2 separate subsets of vertices, where the vertices of one subset connect the other. However, elements in each subset do NOT connect each other

Complete Bitarte Graph

Denoted Km,n, where the graph is bipartite AND every vertex is one set is connected to ALL the vertices in the other

Simple Path

For (u, w) ∈ V(G), a simple path from u to w is a path from u to w with no repeated vertices.

Cycle

A path of non-zero length w/ no repeated edges from u to v, where u, v ∈ V(G).

Simple Cycle

Cycle from u to v in which there are no repeated vertices other than the first and last vertex

Eulerian Cycle

Cycle which includes all edges and all vertices in G

Hamiltonian Cycle

Cycle in G that contains each vertex exactly once (except for the start and end)