Graph Theory Vocab

graph

a finite nonempty set V of vertices and a set E (edges)of 2-element subsets of V

adjacent vertices

vertices connected by an edge

nonadjacent vertices

vertices that are not connected by an edge

neighbor

a vertex adjacent to another vertex

neighborhood

the set of neighbors (adjacent vertices) of a vertex

incident

an edge is "incident" to it's connected vertices

order

number of vertices

size

number of edges

trivial graph

a graph with only one vertex

nontrivial graph

a graph with at least two vertices

empty graph

a graph with no edges

degree

the number of neighbors of a vertex

isolated vertex

a vertex with no neighbors

end vertex

a vertex of degree 1

regular graph

a graph where all vertices have the same degree

proper subgraph

a subgraph that does not equal the graph

induced subgraph

a subgraph containing all of the edges of the graph that have both endpoints in it's subset

spanning subgraph

a subgraph that contains all of the vertices of the original graph

complete graph

a graph where every two distinct vertices are adjacent

complement

a graph with two distinct adjacent vertices if and only if those vertices are nonadjacent in G

isomorphic

two graphs where there exists a bijective function such that two vertices are adjacent in G if and only if they are adjacent in H

multigraph

a graph with parallel edges

parallel edges

multiple edges between the same pair of vertices

loop

an edge joining a vertex to itself

pseudograph

a graph with both parallel edges and loops

walk

a sequence of adjacent vertices of a graph

initial vertex

where a walk begins

terminal vertex

where a walk ends

trivial walk

a walk of length 0

walk length

the number of edges in a walk

trail

a walk with no repeated edges

path

a walk with no repeated vertices

open walk

a walk in which the initial and terminal vertices are not the same

closed walk

a walk in which the initial and terminal vertices are the same

circuit

a closed trail of length 3 or more

cycle

a circuit with no repeated vertices (except the initial/terminal vertex)

even cycle

a cycle of even length

odd cycle

a cycle of odd length

bipartite graph

a graph that can be split into two subsets such that there are only edges between vertices belonging to different subsets

complete bipartite graph

a graph where every vertex of each subset is connected to every vertex of the other subset

k-partite graph

a graph that is partitioned into k subsets

complete multipartite graph

a k-partite graph such that every vertex of each subset is connected to every vertex of every other subset

Eulerian graph

a connected graph that contains a trail or circuit in which every vertex is visited exactly once

Hamiltonian graph

a graph that contains a cycle that visits every vertex of the graph exactly once

weighted graph

a graph in which every edge is assigned a number