Week 7 Lecture 1 Unfilled

Page 1: Overview of Graph Topics

• Introduction: Overview of fundamental graph theory concepts.

• Definitions: Key definitions and terminology related to graphs.

• Connected Graphs & Connected Components: Exploration of connectivity in graphs.

• Simple Graphs: Characteristics of simple graphs.

• Complete Graphs and Cycle Graphs: Discussion on complete graphs (Kn) and cycle graphs (Cn).

• Bipartite Graphs: Types and features of bipartite graphs.

• Subgraphs: Concept of subgraphs and their properties.

• Complement of a Graph: Definition and relevance of complement graphs.

• Handshake Theorem: Explanation of vertex degree and its implications.

• Walks, Trails, Paths, Circuits, Cycles: Different types of graph traversals.

• Eulerian Graphs: Criteria for Eulerian graphs.

• Hamiltonian Graphs: Understanding Hamiltonian graphs.

• Digraphs: Overview of directed graphs.

• Matrices and Adjacency Matrices: Importance of matrices in graph representation.

• Matrix Multiplication: Applications of matrix operations in graph theory.

• Walks of a Given Length: Investigating walks based on specified lengths.

• Trees and Rooted Trees: Characteristics of tree structures in graphs.

• Index of Symbols: Symbols and notation used in graph theory.

Page 2: Complete Graphs and Cycle Graphs

• Definition 5.1: Complete Graph (Kn)

  • A simple graph with n ≥ 1 vertices.

  • Every pair of distinct vertices is connected by an edge.

  • Examples: K1, K2, K3, K4.

• Activity 5.2: Draw Kn for n = 1, 2, 3, 4.

• Activity 5.3: Determine the size (number of edges) in Kn.

• Definition 5.4: Cycle Graph (Cn)

  • A connected simple graph of order n (n ≥ 3).

  • Each vertex has a degree of 2.

Page 3: Bipartite Graphs

• Definition 6.1: Bipartite Graphs

  • Vertex set can be partitioned into two subsets.

  • No edges connect vertices within the same subset.

  • No loops allowed; can allow parallel edges.

• Example 6.2: Examples of bipartite graphs.

• Activity 6.3: Identify which graphs are bipartite.

Page 4: Complete Bipartite Graphs

• Definition 6.4: Complete Bipartite Graph (Km,n)

  • Simple graph with distinct vertices v1, ..., vm and w1, ..., wn.

  • Edges connect each vertex vi to every vertex wj, but no edges between vi or wi.

• Activity 6.5: Draw K1,1, K1,2, K2,2, K2,3.

• Activity 6.6: Determine the order and size of Km,n.

Page 5: Subgraphs

• Definition 7.1: Subgraph

  • H is a subgraph of G if all vertices of H are in G and all edges of H are in G.

  • Induced subgraph is a specific subgraph type.

• Activity 7.2: Assess subgraph relations among given graphs.

• Activity 7.3: Draw subgraphs of K2 and K3.

Page 6: Complement of a Graph

• Definition 8.1: Complement of a Graph G

  • Vertex sets of G and its complement are the same.

  • Two distinct vertices are connected in the complement if not connected in G.

• Activity 8.2: Determine if graphs are complements.

• Activity 8.3: Find complements of specified graphs.

Page 7: Additional Activities

• Activity 8.4: Find the complement of K4 and describe Kn.

• Activity 8.5: Find the complement of K3,4 and describe Km,n.

Page 8: Handshake Theorem

• Definition: Degree of a vertex v is edges incident to it; loops counted twice.

• Activity 9.1: Find vertex degrees and total degree in graph G.

• Remark 9.2: Maximum degree in simple graph of order n is n − 1.

Page 9: Further Activities and Theorem

• Activity 9.3: Find degrees and total degrees in Kn and Km,n.

• Theorem 9.4: The total degree of a graph equals twice the size of the graph.

  • Each edge contributes 2 to total degree.

• Activity 9.5: Verify the Handshake Theorem for specified graphs.

Page 10: Closing Theorems

• Theorem 9.6: The total degree of a graph is even.

• Activity 9.7: Check existence of graphs with specified degrees.

• Activity 9.8: Query on friendship connections among 9 people.

Page 11: Index of Symbols

• Notation:

  • V(G): Vertex set of graph G

  • E(G): Edge set of graph G

  • D(G): Edge set of directed graph G

  • deg(v): Degree of node v

  • Pn: Path graph on n nodes

  • Kn: Complete graph on n nodes

  • Km,n: Complete bipartite graph on m and n nodes

  • Cn: Cycle graph on n nodes

  • G or Gc: Complement of graph G

  • |S|: Cardinality of set S

  • d(u, v): Distance between nodes u and v

  • Ak: k-th power of matrix A