# 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.