12.2 Graph Structures

Graph theory helps us understand connections in networks. It's all about vertices (points) and edges (lines) that link them. We use graphs to model everything from social networks to transportation systems.

The Sum of Degrees Theorem and different types of cycles are key concepts. They help us analyze graph structures and find efficient paths through networks. Understanding these ideas is crucial for solving real-world problems using graphs.

Graph Structures and Properties

Sum of degrees theorem

Top images from around the web for Sum of degrees theorem

• 

  Using the Properties of Triangles to Solve Problems | Developmental Math Emporium View original

  Is this image relevant?

• 

  Vertex (graph theory) - Wikipedia View original

  Is this image relevant?

• 

  Elements of Graph Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Using the Properties of Triangles to Solve Problems | Developmental Math Emporium View original

  Is this image relevant?

• 

  Vertex (graph theory) - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Sum of degrees theorem

• 

  Using the Properties of Triangles to Solve Problems | Developmental Math Emporium View original

  Is this image relevant?

• 

  Vertex (graph theory) - Wikipedia View original

  Is this image relevant?

• 

  Elements of Graph Theory | Mathematics for the Liberal Arts View original

  Is this image relevant?

• 

  Using the Properties of Triangles to Solve Problems | Developmental Math Emporium View original

  Is this image relevant?

• 

  Vertex (graph theory) - Wikipedia View original

  Is this image relevant?

1 of 3

• The degree of a vertex represents the number of edges incident to it
  • In a graph without loops, the degree equals the number of adjacent vertices (neighbors)
• The Sum of Degrees Theorem establishes a relationship between the sum of the degrees of all vertices in a graph and twice the number of edges
  • Theorem: $\sum_{v \in V} \deg(v) = 2|E|$
    • $\sum_{v \in V} \deg(v)$ denotes the sum of the degrees of all vertices in the graph
    • $|E|$ represents the total number of edges in the graph
  • Each edge contributes to the degree of two vertices, explaining why the sum of degrees equals twice the number of edges
  • Examples:
    • In a graph with 5 vertices and 7 edges, the sum of degrees is 14 (2 × 7)
    • For a complete graph $K_4$ with 4 vertices and 6 edges, the sum of degrees is 12 (2 × 6)

Types of cycles in graphs

• A cycle refers to a closed walk with no repeated vertices except for the starting and ending vertex
  • The length of a cycle corresponds to the number of edges it contains
• Types of cycles:
  • Eulerian cycle: A cycle that uses every edge in the graph exactly once
    • A graph containing an Eulerian cycle is known as an Eulerian graph
    • Example: In a graph representing a network of roads, an Eulerian cycle would allow traversing all roads exactly once and returning to the starting point
  • Hamiltonian cycle: A cycle that visits every vertex in the graph exactly once
    • A graph containing a Hamiltonian cycle is called a Hamiltonian graph
    • Example: In a graph representing cities and their connections, a Hamiltonian cycle would represent a route that visits each city exactly once and returns to the starting city
• Cyclic subgraphs:
  • A subgraph consists of a subset of the vertices and edges of a graph
  • A cyclic subgraph contains at least one cycle within it
  • Examples of cyclic subgraphs:
    • Triangles: Cycles of length 3 (3 vertices and 3 edges)
    • Quadrilaterals: Cycles of length 4 (4 vertices and 4 edges)
    • Pentagons: Cycles of length 5 (5 vertices and 5 edges)

Triangle counting in complete graphs

• A complete graph is a graph where every pair of distinct vertices is connected by a unique edge
  • Denoted as $K_n$, where $n$ represents the number of vertices
• The number of triangles in a complete graph can be calculated using the following formula:
  • Number of triangles in $K_n = \binom{n}{3} = \frac{n(n-1)(n-2)}{6}$
    • $\binom{n}{3}$ represents the binomial coefficient, which can be found using Pascal's Triangle
    • Example: In a complete graph $K_5$ with 5 vertices, the number of triangles is $\binom{5}{3} = \frac{5 \times 4 \times 3}{6} = 10$
• Pascal's Triangle:
  • A triangular array of numbers where each number equals the sum of the two numbers directly above it
  • The $k$-th entry in the $n$-th row of Pascal's Triangle represents the binomial coefficient $\binom{n}{k}$
  • To find $\binom{n}{3}$, locate the 3rd entry in the $n$-th row of Pascal's Triangle
  • Example: In the 5th row of Pascal's Triangle (1, 4, 6, 4, 1), the 3rd entry is 6, which equals $\binom{5}{3}$
• Alternative formula for the number of triangles in $K_n$:
  • Number of triangles in $K_n = \frac{|E|(|E|-1)(|E|-2)}{6}$, where $|E| = \frac{n(n-1)}{2}$ is the number of edges in $K_n$
  • Example: In a complete graph $K_6$ with 6 vertices and 15 edges, the number of triangles is $\frac{15 \times 14 \times 13}{6} = 455$

Graph Theory Concepts

• Graph theory is a branch of mathematics that studies the properties and relationships of graphs
• Adjacency matrix: A square matrix used to represent a finite graph, where the element at position (i,j) indicates whether vertices i and j are adjacent
• Directed graph (digraph): A graph in which edges have a direction, represented by arrows
• Connectivity: A property of a graph that measures how well-connected it is
  • A graph is connected if there is a path between every pair of vertices
• Tree: A connected graph with no cycles, where any two vertices are connected by exactly one path
  • Trees are important in many applications, such as representing hierarchical structures