A Tour Through Graph Theory

A graph G consists of two sets:

• V(G), called the vertex set
• E(G), called the edge set.

An edge, denoted xy, is an unordered pair of vertices. We will often use G or G = (V;E) as short-hand.

• If xy is an edge, then x and y are endpoints for that edge. x is incident to edge e if x is an endpoint of e.
• Adjacent edges: share the same endpoint
• Adjacent vertices: share the same edge
• If two vertices are adjacent, they are called neighbors, N(x)
• Isolated vertex: not incident to any edge
• Loop: both endpoints of an edge are the same vertex
• Multi-edge: more than one edge with the same endpoints
• Simple graph: no multi-edges or loops
• Degree of a vertex: number of edges incident to vertex, deg(v)
  • Loop adds 2 to degree

Bipartite graph: interactions between two distinct types of groups