Graph Theory Definitions:

Define - Bipartite Graph:

A graph whose set of vertices can be split into two distinct groups in such a way that each edge of the graph joins a vertex in the first group to a vertex in the second.

Define - Complete Graph:

A simple graph in which every vertex is joined to every other vertex by an edge. The complete graph with n vertices is denoted Kn.

A complete bipartite graph is a bipartite graph where every vertex of the first set is connected to every vertex of the second set.

Define - Connected Graph:

A graph is connected if there is a path between each pair of vertices.

A bridge is an edge in a connected that if removed leaves a graph disconnected.

Define - Cycle:

A closed path which begins & ends at the same vertex with no repeated edges or vetices except the first.

Define - Degree of a Vertex (Graph):

In a graph the degree of a vertex is the number of edges that enter or exit from the vertex, thus loops are counted twice.

Define - Directed Graph:

A directed graph is a diagram comprising points, called vertices, joined by directed lines called arcs - directed graphs are commonly called digraphs.

Euler’s Formula:

For a connected planar graph, Euler’s rule states that v + f - e = 2, where v is the number vertices, e is the number of edges & f is the number of faces.

Define - Eulerian Graph

A connected graph is Eularian if it has a closed trail (starts & ends at the same vertex), that is includes every edge & once only; such a trail is called an Eularian trail.

An Eularian trail may include repeated vertices.

A connected graph is semi-Eularian if there is an open trail that includes every edge once only.

Define - Loop:

A loop is an edge in a graph that joins a vertex in a graph to itself

Define - Multiple Edge:

A multiple edge is where two or more edges connect the same vertices.

Define - Hamiltonian Graph:

A connected graph is Hamiltonian if it contains a closed path (starts & ends at the same vertex), that includes every vertex (except the first one) once only.

No edge is repeated.

Define - Semi-Hamiltonian Graph:

Contains a path that includes every vertex in a graph once only but is not a cycle.

Define - Length of a Walk

The number of edges it includes

Define - Open Path

A path that starts & finishes at different vertices is said to be open.

Define - Open Walk

A walk that starts & finishes at different vertices is said to be an open walk.

Define - Path

A path in a graph is a walk in which all edges & vertices are different.

Define - Closed Path

A path that starts & finishes at the same vertex - a cycle is a closed path.

Define - Planar Graph:

A planar graph is a graph that can be drawn in the plane so that no two edges cross.

Define - Semi-Eulerian Graph

A connected graph is semi-Eulerian if there is an open trail that includes every edge once only

Define - Simple Graph:

A graph that has no loops or multiple edges

Define - Subgraph

When the vertices & edges of a graph are also vertices & edges of another graph is said to be a subgraph of graph G.

Define - Trail:

A trail is a walk in which no edge is repeated

Define - Walk:

A sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence.

A walk can include repeated vertices or repeated edges

Define - Weighted Graph:

A graph in which each edge is labelled with a number used to represent some quantity associated with that edge