Graphs

Types of Graph

Undirected Graph

An undirected graph $G$ consists of 2 finite sets: a nonempty set of $V$ vertices and a set $E$ of edges, where each edge is associated with a set consisting of either one or two vertices called its endpoints.
An edge is said to connect its endpoints. Two vertices that are connected to an edge are called adjacent vertices (vertices can be adjacent to themselves).
An edge is said to be incident on each of its endpoints, and two edges incident on the same endpoint are called adjacent edges. Denoted $G=(V,E)$ where

• $V=\{v_1,v_2,\dots ,v_n\}$ is the set of vertices (or nodes) in $G$
• $E=\{e_1,e_2,\dots ,e_k\}$ is the set of undirected edges in $G$
• An undirected edge $e$ connecting $v_i$ and $v_j$ is denoted $e=\{v_i,v_j\}$

Directed Graph

Definition is same as Undirected Graph, except $E$ is a set of ordered pairs, representing directed edges. An edge from $v$ to $w$ is $e=(v,w)$

Subgraph

A graph $H$ is said to be a subgraph of $G$ iff every vertex in $H$ is also a vertex in $G$ , every edge in $H$ is also an edge in $G$ , and has the same endpoints as it has in $G$

Simple Graph

An undirected graph that does not have any loops or parallel edges (no pair of vertices has two edges between them)

Complete Graph

A complete graph on $n$ vertices, $n>0$, denoted $K_n$ is a simple graph with $n$ vertices and exactly one edge connecting each pair of distinct vertices. $K_n$ has $n(n-1)/2$ edges.

Bipartite Graph

(or bigraph) is a simple graph whose vertices can be divided into two disjoin sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$

Complete Bitartite Graph

A bigraph on two disjoint sets $U$ and $V$ such that every vertex in $U$ connects to every vertex in $V$ . If $|U|=m$ and $|V|=n$ , the complete bipartite graph is denoted as $K_{m,n}$

Definitions

Degree of Undirected Graph

• Degree of vertex $v$, denoted deg($v$) is the number of edges that are incident on $v$ , with an edge that is a loop counted twice.
• Total degree of $G$ is the sum of the degrees of all the vertices of $G$

Indegree and Outdegree of Directed Graph

• Indegree of vertex $v$ denoted $de{g}^{-}(v)$ is the number of directed edges that end at $v$
• Outdegree of vertex $v$ denoted by $de{g}^{+}(v)$ is the number of directed edges that originate from $v$
• ${\sum }_{v\in V}de{g}^{-}(v)={\sum }_{v\in V}de{g}^{+}(v)=|E|$

Traversing

• Walk: a walk from $v$ to $w$ is a finite alternating sequence of adjacent vertices and edges of $G$
  • It has the form $v_0{e}_1{v}_1{e}_2\dots v_{n-1}{e}_n{v}_n$ where $v_0=v,v_n=w$ and for all $i\in 1,2,\dots ,n$ $v_i-1$ and $v_i$ are the endpoints of $e_i$
  • The number of edges $n$ is the length of the walk
  • The trivial walk from $v$ to $v$ consists of the single vertex $v$
• Trail: a walk that does not contain a repeated edge
• Path: a trail that does not contain a repeated vertex
• Closed Walk: a walk that starts and ends at the same vertex
• Cycle or circuit: a closed walk of length at least 3 that does not contain a repeated edge
• Simple cycle or simple circuit: a circuit that does not have any other repeated vertex except its first and last
• Cyclic: An undirected graph is cyclic if it contains a loop or cycle. Otherwise, it is acyclic

Euler Circuit

• An euler circuit for $G$ is a circuit that contains every vertex and traverses every edge of $G$ exactly once
• An eulerian graph is a graph that contains an euler circuit
• Theorem 10.2.2: If a graph has an Euler circuit, then every vertex of the graph has positive even degree (contrapositive: if some vertex of a graph has odd degree, then the graph does not have an euler circuit)
• Theorem 10.2.3: If a graph $G$ is connected and the degree of every vertex of $G$ is a positive even integer, then $G$ has an euler circuit
• Theorem 10.2.4: A graph $G$ has an euler circuit iff $G$ is connected and every vertex of $G$ has positive even degree

Euler Trail/path

• An euler trail/path from $v$ to $w$ is a sequence of adjacent edges and vertices that starts at $v$ , ends at $w$ , passes through every vertex of $G$ at least once, and traverses every edge of $G$ exactly once. (Euler circuit but doesn’t need to start and end at the same vertex)
• Corollary 10.2.5: There is an euler trail from $v$ to $w$ iff $G$ is connected, $v$ and $w$ have odd degree, and all other vertices of $G$ have positive even degree

Hamiltonian Circuit

• A simple circuit that includes every vertex of $G$ (every vertex appears exactly once, except for the first and the last, which are the same)
• Hamiltonian graph: a graph that contains a hamiltonian circuit
• Proposition 10.2.6: If graph $G$ has a hamiltonian circuit, then it has a subgraph $H$ with the following properties
  • $H$ contains every vertex of $G$
  • $H$ is connected
  • $H$ has the same number of edges as vertices
  • Every vertex of $H$ has degree 2

Connectedness

• Two vertices of a graph are connected iff there is a walk from $v$ to $w$
• The graph $G$ is connected iff for any two vertices $v$ and $w$ in $G$ , there is a walk from $v$ to $w$
• A graph $H$ is a connected component of a graph $G$ iff all of the following:
  • The graph $H$ is a subgraph of $G$
  • The graph $H$ is connected
  • No connected subgraph of $G$ has $H$ as a subgraph and contains edges or vertices that are not in $H$ (It is the biggest possible, contains as many edges and vertices as possible)
• Lemma 10.2.1
  • If $G$ is connected, then any two distinct vertices of $G$ can be connected by a path
  • If vertices $v$ and $w$ are part of a circuit in $G$ and one edge is removed from the circuit, then there still exists a trail from $v$ to $w$ in $G$
  • If $G$ is connected and $G$ contains a circuit, then an edge of the circuit can be removed without disconnecting $G$

Handshake Theorem

Theorem 10.1.1: The total degree of a graph $G$ is 2 times the number of edges of $G$

• The total degree of a graph is even
• In any graph, there are an even number of vertices of odd degree

Matrix representation of graph

Note: $a_{ij}$ represents the element at the ith row and jth column of A. A $m\times n$ matrix has m columns and n rows

Adjacency Matrix

Let $G$ be a directed graph with ordered vertices $v_1,v_2,\dots v_n$
The adjacency matrix of $G$ is the $n\times n$ matrix $A=(a_{ij})$ over the set of non-negative integers such that: $a_{ij}=$ the number of arrows from $v_i$ to $v_j$ for all $i,j=1,2,\dots ,n$
i.e. the element at the ith row and jth column is the number of edges from the ith vertex to the jth vertex
Note: an adjacency matrix of an undirected graph is symmetric (about the top-left to bottom-right diagonal)

Counting walks of length n

Theorem 10.3.2: If $A$ is the adjacency matrix of a graph, the i j-th entry of $A^n$ is the number of walks of length $n$ connecting the ith and jth vertices of the graph.

Matrix Operations

Scalar Product

The scalar product or dot product of the ith row of $A$ and jth column of $B$ (where the number of elements in both are the same) is the sum of the individual products ($a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+...+a_{in}{b}_{nj}$)

Matrix multiplication

The matrix product of $A$ and $B$ (number of cols in $A$ must be the same as the number of rows in $B$).
The matrix product is a matrix $C$ where the element $c_{ij}$ is the scalar product of row i of matrix $A$ and column j of matrix $B$

Identity matrix

The main diagonal is all 1s, the rest is 0.

$n^{th}$ power of a matrix

For matrix $A$ , $A^n=A{A}^{n-1}$ , so $A^3=A(AA)$

Isomorphism of graphs

Let $G=(V_G,E_G)$ and $G^{\prime }=(V_{G^{\prime }},E_{G^{\prime }})$ be two graphs.
$G$ is isomorphic to $G^{\prime }$ , denoted $G\cong G^{\prime }$ iff there exists bijections: $g:V_G\to V_{G^{\prime }}$ and $h:E_G\to E_{G^{\prime }}$ that preserve the edge-endpoint functions of $G$ and $G^{\prime }$ in the sense that for all $v\in V_G$ and $e\in E_G$ , $v$ is an endpoint of $e\iff g(v)$ is an endpoint of $h(e)$
(The graphs have the same shape after re-arranging)
Alternately: Let $G=(V_G,E_G)$ and $G^{\prime }=(V_{G^{\prime }},E_{G^{\prime }})$ be two simple graphs. $G$ is isomorphic to $G^{\prime }$ iff there exists a permutation (function) $\pi :V_G\to V_{G^{\prime }}$ such that $\{u,v\}\in E_G\iff \{\pi (u),\pi (v)\}\in E_{G^{\prime }}$
Theorem 10.4.1: Graph isomorphism is an equivalence relation

Planar Graph

A planar graph can be drawn on a two-dimensional plane without edges crossing

Kuratowski’s Theorem

A finite graph is planar iff it does not contain a subgraph that is a subdivision of the complete graph $K_5$ or the complete bigraph $K_{3,3}$ (subdivision: a graph that is made by placing a vertex along any edge to turn it into two edges)

Euler’s Formula

For a connected planar simple graph $G=(V,E)$ with $e=|E|$ and $v=|V|$ , if we let $f$ be the number of faces, then $f=e-v+2$ (a face is a region bound by edges of a planar graph when it is drawn without overlapping edges. note: the area outside the whole graph is counted as a face)