Graphs

• Simple graph: Undirected graph, no loops (distinct vertices) and no multiedges (set of edges is a set of unordered pairs)
• Multi graph: Undirected, no loops but multiple edges are allowed
• Pseudo graph: Same as multigraph but allows loops.
• Def. 4 and 5 apply to directed graphs. The first one doesn't allow multiple edges, second one allows multiple edges.
• Page 433 warns you about different terminology you may come across during your further reading from other documents.
• Read the examples from 7.1 so that you are aware of some of the applications of graph theory.

Basic Terminology

• Definition 1: adjacent vertices, edge incident with vertices, connect, endpoints.
• Definition 2: Degree of a vertex - each edge contributes 1 to the degree, a loop contributes two to the degree.
• Theorem 1 and theorem 2 (proof with an example from board)
• Definition 3: adjacent to, adjacent from, initial vertex and end vertex.
• Definition 4: in-degree (number of edges coming in), out-degree (number of edges going out)
• Theorem 3.
• How many edges does Kn have? (n^2-n)/2
• Cycles Cn (n vertices and n edges), Wheels Wn (n+1 vertices and 2n edges)
• n-Cubes Qn (2^n vertices and n*2^(n-1) edges)
• Bipartite graphs
  • If you can partition the set of vertices into two subsets such that there are no edges between all the vertices in a subset, then the graph is called a bipartite graph.
  • Complete bipartite graph km,n (m+n vertices and m*n edges)
• Subgraph: G=(V,E) is a subgraph of H=(W,F) if V is a subset of W and E is a subset of F.
• Union of G=(V,E) and H=(W,F) is given by (V U W, E U F) = G U H

Graph Representation

• Three different representations

1. Adjacency lists
2. Adjacency matrices
3. Incidence matrices

• Adjacency lists: For every vertex, you list all the vertices that are adjacent to it
• Adjacency matrix: If there is an edge from v_i to v_j then a_ij=1 otherwise a_ij=0. For multigraphs a_ij will be the number of edges between v_i and v_j. The matrices for simple graph as well as the multigraph are symmetric and have diagonal elements equal to 0. Matrices for pseudograph will still be symmetric but the diagonal elements may be non-zero. For directed graphs the matrices are neither symmetric nor have all-zeroes in the diagonal.
• Incidence matrix: There is a column for every edge and there is a row for every vertex. If an e_j is incident with v_i then a_ij=1.
• Let us assume that you have m edges n of them are loops and p vertices. How many zero elements will you have in an incidence matrix? m*p - (2*m-n)

Isomorphism

• Definition 1
• Example 8.
• In general, difficult to prove whether two graphs are isomorphic. We need to try n! combinations.
• Invariants
  • If the number of vertices or edges in two graphs are not the same, those two graphs are not isomorphic.
  • If there is m vertices with degree n in one graph, and k number of vertices with degree n in one graph and k!=n, then the two graphs are not isomorphic.
• Example 10 and example 11
• In general, you can reduce the number of possible mappings, using the degree of vertices. A vertex with degree m can only be mapped to another vertex with degree m.

Connectivity

• Definition of a path:
  • The mapping need not be mentioned for a simple graph. The path for simple graph can be written as x0,x1,x2,......,xn.
  • Circuit: if x0 and xn are the same then the path is a circuit or a cycle.
  • Path x0,x1,x2,......,xn is said to pass through the vertices x0,x1,x2,......,xn.
  • Simple path: No vertex (as opposed to edge) is repeated more than once.
• Definition 2: defines the path for a digraph.
• Definition 3: Connected graph.
• If a graph is not connected, we can find two or more connected components for the graph. Connected components are subgraphs of the original graph and they don't have any vertices in common.
• cut vertex or articulation point: If there is a vertex in the graph such that when you remove the vertex along with incident edges, the graph is no longer connected.
• cut edge or bridge: If there is an edge in the graph such that when you remove the edge, the graph is no longer connected.
• Theorem 1: Proof by contradiction
• For the digraphs, we define strong and weak connectivity.
• Strong connectivity: there is a path from one vertex to every other vertex in the digraph
• Weak connectivity: there is a path from one vertex to every other vertex in the underlying undirected graph of the digraph.
  • Underlying undirected graph means you ignore the direction in the digraph.
• An additional invariant for checking for the isomorphism: If a graph has a simple circuit of length m, and the other graph doesn't have a simple circuit of length m then they are not isomorphic.
• Theorem 2: How many paths of length r between vi and vj

Euler circuit

• Definition, theorem 1 and theorem 2
• Problem 38
• Km,n: has two sets of vertices first with m vertices and second with n vertices
• vertices in first set have a degree of n and vertices in the second set have a degree of m.
• For Euler circuit all the degrees have to be even
• For part b, we include Km,n from part a
• in addition we can have a few Km,n where m is odd, how many vertices can we have in the second set? Remember that degree of vertices in the second set is going to be odd. Look at theorem 2.
• Constructing an Euler circuit
  • page 476

Hamiltonian Circuit

• You pass through a vertex only once, different from Euler circuit, where we were allowed to pass through a vertex more than once
• Hamilton circuit may not pass through every edge.
• There is no condition which is both necessary and sufficient
• There are several sufficient conditions: Theorem 3.
• Problem 52: It does exist

Planar graphs

• Definition
• Euler formula
• Corollary 1 proves that K5 is not planar
  • Degree of a region bottom of page 503
• Corollary 2 proves that K3,3 is not planar
• Problem 16
  • Connect the K components to get a connected planar graph
  • The additional edges is k-1, doesn't add any new regions
  • apply the Euler formula

Coloring problem

• Map, exam schedules can be converted to graphs
  • Every region in the map is a vertex in the graph. If the regions are adjacent then there is an edge between the corresponding vertices
  • Exam schedule: every class is a vertex. If one or more students are taking two different classes then there is an edge between the corresponding vertices
• Definition 1. graph coloring
• The maximum number of colors to color a graph with n vertices is n. Not very interesting problem
• Def. 2: Chromatic number - minimum number of colors required to color a graph
• Theorem 1. A planar graph can be colored with atmost 4 colors.
• Quiz shows how to color a graph and find chromatic number
  • 4, 6 and 8 are related to coloring a given graph
  • 4 can be done with three, 6 definitely can be done with 4 because it is planar. Can 6 be done with 3?
  • 8: the vertices i,b,h,c are connected to each other to form a K4. We atleast need 4 colors. Start by coloring them in different colors.
• Kn needs n colors. Because no two vertices can have the same color
• Cn 2 or 3 depending on whether n is odd or even.
• Problem 20:
  • edge chromatic number
  • Kn we can see that n-1 might be a possible answer, every edge coming of a vertex gets different color
  • Km,n assume m>=n. maximum degree is m. that can be the number of colors
  • Cn?
  • Wn: The vertex in the middle has a degree of n