Mathematics of graph

• A graph is a collection of vertices also called points or nodes and edges also called lines
• A vertex or node is a thing; it is an entity that we can ascribe some value to it
• Edges can be defined as a relation of some sort between two or more nodes
• The number of vertices in a graph is called its ORDER (p)
• The number of edges on a graph is called its SIZE (q)
• Order (p)= 5

  Size (q)= 6

  
• The ends of an edge are said to be INCIDENT with the edge and vice versa.
• Two vertices which are incident with a common edge are ADJACENT as are two edges which are incident with a common vertex
• Incident is equal to the number of edges or size (p)
• An edge with identical ends is called a loop
• An edge with distinct edges is called a link
• Graph with just one vertex

  Trivial graph
• A graph with no loops and no two of its links join the same pair of vertices

  Simple graph
• Simple graph

  
• A simple graph in which each pair of distinct vertices is joined by an edge. Denoted as Kn.

  Complete Graph
• Complete graph

  
• A graph with no edges

  Empty graph 
• Empty graph

  
• The degree of a vertex v is the number of edges of G incident with v, each loop counted as two edges. This is denoted by d(v)

  
• The sum of the degrees of all vertices in a graph is equal to twice the number of edges of the graph.
• A walk in a graph is an alternating sequence of vertices and edges, beginning and ending with vertices.
• The length of a walk is the number of edges it encounters.
• A walk with 0 length is called a trivial walk
• A walk in which no edge is repeated

  Trail
• A trail in which no vertex is repeated

  Path
• Connected graph

  
• Disconnected graph

  
• A trail that begins and ends in the same vertex; A nontrivial trail with no repeated edges.

  Circuit
• A path that begins and ends in the same vertex; A closed path with no repeated edges and vertices except the first and last.

  Cycle
• One of the most prolific mathematicians ever, was able to solve this problem in 1735, by introducing edges representing the bridges and vertices representing the land masses. This laid the foundation for graph theory as a field in mathematics.

  Leonard Euler
• A trail that transverses every edge

  Euler trail
• A closed walk that transverses each edge of G at least once.

  Tour of G
• A tour which transverses each edge exactly once

  Euler tour
• A graph is Eulerian if it contains an EULER TOUR
• A nonempty connected graph is eulerian if and only if it has no vertices of odd degree
• Corollary 


  A nonempty graph has an Euler trail if and only if it has 0 or two vertices of odd degree
• A path that contains every vertex of G

  HAMILTONIAN PATH OF G
• In Hamiltonian path, the edges of the graph may or may not all be covered since edges and vertices must not repeat
• A cycle that contains every vertex of G

  HAMILTONIAN CYCLE OF G
• A graph is Hamiltonian if it contains a Hamiltonian cycle