Graph Theory - definitions, relationships
Graph is made up of vertices, which are connected by edges.
The degree of the vertex, is the number of edges of that vertex.
(By convention, we count a loop twice and parallel edges contribute separately)
For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex and the number of tail ends adjacent to a vertex is its outdegree.
Regular graph is a graph where each vertex has the same degree.
Edges that have the same end vertices are parallel.
Loop is an edge that connects a vertex to itself.
An isolated vertex is a vertex whose degree is 0 (no vertices).
A graph with no edges is an empty grpaph.
A graph is simple if it has no parallel edges or loops.
A simple graph that contains every possible edge between all the vertices is called a complete graph.
A planar graph is a graph that can be embedded in the plane (no crossing vertices).
A walk: is a sequence whose terms alternate between vertices and edges (not necessarily distinct).
A trail is a walk such that all of the edges are distinct.
A path is a trail with no repeated vertex.
A cycle is a closed path.
A graph is connected when there is a path between every pair of vertices.
Eulerian trail (or Eulerian path) is a trail which visits every edge exactly once.
Hamiltonian path is a path that visits each vertex exactly once.
Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.
A tree is an undirected graph in which any two vertices are connected by exactly one path.
Number of vertices=number of edges+1
Forest: every component is a tree.
Number of vertices=number of edges+number of components.