# A Tour Through Graph Theory

Jump to navigation
Jump to search

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