Mathematics of Graphs

• Leonhard Euler


  The greatest mathematician that Switzerland has ever produced.
• Mathematics of graph


  A branch of mathematics concerning with network of points connected by lines
• Vertex


  A region
• Edge


  a path(bridge) between two regions
• Order


  The number of vertices in G, 𝑣(𝐺)
• Size


  The number of edges in G, 𝑒(𝐺)
• Loop


  An edge whose endpoints are equal
• Multiple edges


  Edges have the same pair of endpoint
• Simple graph


  A graph has no loops or multiple edges
• Null graph


  the graph whose vertex set and edges are empty
• Finite graph


  a graph whose vertex set and edge set are finite
• Equivalent graphs


  Graphs are considered ____ because the edges form the same connections of vertices in each graph.
• Clique


  a set of pairwise adjacent vertices
• Independent set


  a set of pairwise nonadjacent vertices
• Bipartite


  A graph 𝑮 is ____ if 𝑽(𝑮) is the union of two disjoint independent sets called partite sets of 𝑮
• Chromatic number


  The ____ of a graph 𝑮, written 𝒙(𝑮), is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors
• Map


  a partition of the plane into connected regions
• Path


  a sequence of distinct vertices such that two consecutive vertices are adjacent
• Cycle


  a closed path
• Connected


  There exists at least one path between two vertices
• Disconnected


  No path between two vertices
• Degree


  the number of edges incident upon d(Vk)
• Adjacency matrix


  The ____ of G written A(G), is the n-by-n matrix in which entry ai,j is the number of edges in G with endpoints {vi , vj }.
• Incidence matrix


  The ____ is the n-by-m matrix in which entry mi,j is 1 if vi is an endpoint of ei and otherwise is 0.
• Complete graph


  a simple graph whose vertices are pairwise adjacent
• Biclique


  a simple bipartite graph such that two vertices are adjacent if and only if they are in different partite sets.
• Petersen graph


  A simple graph whose vertices are the 2-element subsets of a 5-element set and whose edges are pairs of disjoint 2-element subsets
• Girth


  the length of its shortest cycle
• Walk


  a list of vertices and edges
• Trail


  a walk with no repeated edge
• u,v-path


  a u,v-trail with no repeated vertex
• Length


  the number of edges
• Closed


  A walk or trail is ____ if its endpoints are the same.
• Even graph


  a graph with vertex degrees all even
• Odd


  A vertex is ____ when its degree is odd.
• Transversable graph


  A graph that can be drawn without any breaks in the curve without repeating any edge.
• Eulerian


  The graph is ____ if it has a closed traversable trail.
• HAMILTONIAN GRAPH


  A graph with a closed path that passes through all vertices exactly once.
• Circuit


  We call a closed trail a ____ when we do not specify the first vertex but keep the list in cyclic order.
• Eulerian trail


  a circuit or trail containing all the edges