Graph Theory Math 332

graph

a non-empty set of vertices C and edges E that connect pairs of vertices.

order

number of vertices of G

size

number of edges of G

loop

an edge that connects a vertex to itself

simple graphs

graphs without loops

adjacent vertices

2 nodes connected directly by a single edge

neighbors

two adjacent vertices

neighborhood

the collection of all the neighbors of a vertex v, N(v)

degree

total number of neighbors of vertex v

adjacent edges

edges that share a common vertex

path

a path starting at u and ending at v, only using edges and vertices of graph G

cycle

closed path where the only repeating vertices are the first and last vertex

subgraph

H is a subgroup of G if all vertices and edges in H belong to G

induced subgraph

A subgraph F of graph G is an induced subgraph if the same two vertices make an edge in both F and G

spanning subgraph

a subgraph H of G that includes every vertex of G

length (of a walk)

total number of edges (counting repeats) in a walk

distance

shortest path between u and v