Graph theory and trees notes — Unit 5

A graph $G = (V, E)$ consists of a non-empty set of vertices $V$ and a set of edges $E$. In discrete mathematics, we focus heavily on the formal properties and classifications of these graphs.

⇒1.1 Basic Terminology

• Degree of a Vertex $\deg(v)$: The number of edges incident to it. A self-loop contributes 2 to the degree.
• Isolated Vertex: A vertex with degree 0.
• Pendant Vertex: A vertex with degree 1.
• Simple Graph: A graph with no self-loops and no parallel (multiple) edges between the same pair of vertices.
• Multigraph: A graph that allows parallel edges.
• Pseudograph: A graph that allows both parallel edges and self-loops.

One of the most fundamental theorems in Graph Theory.

⇒2.1 Statement

In any undirected graph, the sum of the degrees of all vertices is exactly twice the number of edges.

$\sum_{v \in V} \deg(v) = 2|E|$

⇒2.2 Why is it true?

Every edge connects two vertices. When we sum the degrees of all vertices, every edge is counted exactly twice (once at each of its endpoints).

⇒2.3 Important Corollary

In any graph, the number of vertices with an odd degree must be even. (If there were an odd number of odd-degree vertices, the sum of all degrees would be odd, violating the Handshaking Theorem).

⇒3.1 Complete Graph ($K_n$)

A simple graph where every pair of distinct vertices is connected by a unique edge.
Number of edges in $K_n = \frac{n(n-1)}{2}$.

⇒3.2 Regular Graph

A graph where every vertex has the exact same degree. If every vertex has degree $r$, it is called an $r$-regular graph. (Note: A complete graph $K_n$ is an $(n-1)$-regular graph).

⇒3.3 Bipartite Graph

A graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$. There are no edges within $U$ or within $V$.

⇒3.4 Complete Bipartite Graph ($K_{m,n}$)

A bipartite graph where every vertex in set $U$ (size $m$) is connected to every vertex in set $V$ (size $n$).
Number of edges = $m \times n$.

Two graphs $G_1$ and $G_2$ are Isomorphic if they contain the exact same number of graph vertices connected in the exact same way, even if they are drawn differently or their vertices have different labels.

⇒4.1 Necessary Conditions

For $G_1$ and $G_2$ to be isomorphic, they MUST have:

• 1. The same number of vertices.
• 2. The same number of edges.
• 3. The same degree sequence (the list of degrees of all vertices, sorted).

However, these conditions are necessary but not sufficient. Two graphs can share all three properties and still not be isomorphic.

⇒4.2 Formal Definition

A bijective function $f: V_1 \to V_2$ exists such that any two vertices $u, v \in V_1$ are adjacent in $G_1$ if and only if $f(u)$ and $f(v)$ are adjacent in $G_2$.

Originated from the famous 'Seven Bridges of Königsberg' problem.

• Euler Path: A continuous path in a graph that visits every edge exactly once.
• Euler Circuit: An Euler path that starts and ends at the exact same vertex.

⇒5.1 Euler's Theorems

We can determine if a graph has an Euler circuit or path purely by looking at vertex degrees (without needing to trace it!).

• Euler Circuit Theorem: A connected multigraph has an Euler circuit if and only if every vertex has an even degree.
• Euler Path Theorem: A connected multigraph has an Euler path (but not a circuit) if and only if it has exactly two vertices of odd degree. (The path must start at one odd vertex and end at the other).

While Eulerian concepts deal with visiting every edge, Hamiltonian concepts deal with visiting every vertex.

• Hamiltonian Path: A path that visits every vertex exactly once.
• Hamiltonian Circuit: A cycle that visits every vertex exactly once and returns to the starting vertex.

⇒6.1 The Challenge

Unlike Euler circuits, there is no simple degree-based rule to determine if a graph has a Hamiltonian circuit. Finding one is an NP-Complete problem (the famous Traveling Salesperson Problem is a weighted version of this).

⇒6.2 Sufficient (but not necessary) Theorems

• Dirac's Theorem: If $G$ is a simple graph with $n \ge 3$ vertices, and the degree of every vertex is $\ge n/2$, then $G$ has a Hamiltonian circuit.
• Ore's Theorem: If $\deg(u) + \deg(v) \ge n$ for every pair of non-adjacent vertices $u, v$, then $G$ has a Hamiltonian circuit.

A graph is Planar if it can be drawn on a flat 2D plane without any of its edges crossing over one another.

⇒7.1 Regions (Faces)

A planar representation of a graph splits the plane into regions, including one infinite exterior region.

⇒7.2 Euler's Formula for Planar Graphs

For any connected planar graph, the relationship between Vertices ($v$), Edges ($e$), and Regions/Faces ($r$) is strictly fixed:

$v - e + r = 2$

Example: A cube drawn on a plane has 8 vertices, 12 edges, and 6 faces. $8 - 12 + 6 = 2$.

How do we prove a graph is NOT planar? We use inequalities derived from Euler's formula.

• If a connected planar simple graph has $v \ge 3$, then $e \le 3v - 6$.
• If it has no triangles (bipartite), then $e \le 2v - 4$.

Using these, we can mathematically prove that $K_5$ (complete graph with 5 nodes) and $K_{3,3}$ (complete bipartite graph with 3+3 nodes) are non-planar.

⇒8.1 Kuratowski's Theorem

The ultimate test for planarity. A graph is non-planar if and only if it contains a subgraph that is homeomorphic (equivalent via edge subdivisions) to either $K_5$ or $K_{3,3}$.

In simpler terms: $K_5$ and $K_{3,3}$ are the 'building blocks' of non-planarity. If your graph hides either of them inside it, it cannot be drawn without crossing lines. (Highly relevant in PCB circuit design).

Graph coloring involves assigning a color to each vertex of a graph such that no two adjacent vertices share the same color.

⇒9.1 Chromatic Number ($\chi(G)$)

The Chromatic Number is the minimum number of colors required to color the graph validly.

• Complete Graph $K_n$: $\chi = n$ (every vertex connects to every other).
• Bipartite Graph: $\chi = 2$.
• Cycle Graph $C_n$: $\chi = 2$ if $n$ is even, $\chi = 3$ if $n$ is odd.
• Tree: $\chi = 2$.

⇒9.2 The Four Color Theorem

Any planar graph can be colored using no more than 4 colors. (This implies any geographical map can be colored with 4 colors so no adjacent countries share a color).

In discrete math, a Tree is defined as a connected undirected graph with no simple circuits (acyclic).

⇒10.1 Equivalent Definitions

A graph $G$ with $n$ vertices is a tree if it satisfies any of the following equivalent properties:

• It is connected and has exactly $n - 1$ edges.
• It has no cycles, and has exactly $n - 1$ edges.
• There is a unique simple path between any two of its vertices.
• Adding any single edge creates exactly one cycle.
• Removing any single edge disconnects the graph (every edge is a bridge).

A Rooted Tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

⇒11.1 $m$-ary Tree

A rooted tree is called an $m$-ary tree if every internal vertex has no more than $m$ children.

• If $m=2$, it is a Binary Tree.
• If every internal vertex has exactly $m$ children, it is a full $m$-ary tree.

⇒11.2 Node Calculations in Full $m$-ary Trees

Let $n$ be total nodes, $i$ be internal nodes, and $l$ be leaves. Mathematical relationships include:

• $n = m \cdot i + 1$
• $l = (m - 1)i + 1$
• $i = (l - 1) / (m - 1)$

Example: In a full binary tree ($m=2$), $l = i + 1$. The number of leaves is always exactly one more than the number of internal nodes.

A Spanning Tree of a connected graph is a subgraph that contains all vertices of the graph and is a tree.

Every connected graph has at least one spanning tree. We form it by removing edges from circuits until no circuits remain, while keeping the graph connected.

⇒12.1 Edges to Remove

If a connected graph has $v$ vertices and $e$ edges, the spanning tree will have $v - 1$ edges. Therefore, the number of edges that must be removed to create a spanning tree is:

$e - (v - 1) = e - v + 1$

This number is called the Circuit Rank or Cyclomatic Number of the graph.

How many different spanning trees exist for a given graph?

⇒13.1 Cayley's Formula

For a Complete Graph $K_n$ (where every node connects to every other node), the number of distinct labeled spanning trees is given by:

$n^{n-2}$

Example: For $K_4$ (4 vertices, 6 edges), there are $4^{4-2} = 4^2 = 16$ distinct spanning trees.

⇒13.2 Matrix Tree Theorem (Kirchhoff's Theorem)

For a general graph (not necessarily complete), the number of spanning trees can be found by constructing the Laplacian matrix of the graph and calculating the determinant of any of its cofactors.

This concludes Discrete Structures and Theory of Logic.

⇒14.1 University Exam Checklist

• Use the Handshaking Theorem to prove statements about vertex degrees.
• Determine if two given graphs are isomorphic by checking degrees and adjacencies.
• Identify whether a graph contains an Euler path/circuit based on odd/even vertex degrees.
• Apply Euler's formula ($v - e + r = 2$) to planar graphs.
• Calculate the Chromatic number of given standard graphs.
• Use the tree formulas ($n = mi + 1$) to find the number of leaves or internal nodes.

⇒14.2 Computer Science Integrations

• Graph Coloring: Used in compiler design for Register Allocation. Variables that are live at the same time are adjacent vertices; the chromatic number dictates the minimum hardware registers needed.
• Euler Circuits: Used in DNA sequencing and bioinformatics.
• Planarity: Used in VLSI (chip) design to avoid circuit shorting.