Discrete Mathematics Graph Theory: Concepts and Applications from Bemacs

Discrete Mathematics: Graph Theory Introduction

Mathematics Mod. II
30400 BEMACS
Class 25
D Fein
A.Y. 2024-2025
Discrete mathematics
Graph theory
Lesson 1

• Graphs
• Key terminology
• Special graphsThe origin story: The bridges of Königsberg
  The town of Königsberg, Prussia,
  was divided into four sections by
  branches of the Pregel river. In the
  1700s, there were 7 bridges
  connecting these regions.
  "The question is whether a person
  can plan a walk in such a way that
  he will cross each of these bridges
  once but not more than once."
  -Euler 1736
  Comment. Acad. Sc.Tom VIII. Tab. VIII. p. 12.8.
  Hohe B.
  D
  Hormigón.
  Fig. 1.
  . B
  18 20
  The town still exists but is now called
  Kaliningrad in Russia. There are only 5
  bridges still standing, 2 of which date back
  to Euler's time.The solution led to graph theory!

Euler's Contribution to Graph Theory

In his 1736 paper solving the age-old problem, Euler effectively invented
graph theory.

• The 4 land masses are represented by 4 vertices (or nodes).
• The 7 bridges are represented by 7 edges.
  c
  9
  C
  A
  €
  D
  6
  a
  B
  C
  D
  A
  B
  We will find the solution
  soon!A graph

Graph Definition and Properties

: Order
/VI
TEL : Size
O. S.
Definition
A graph G = (V, E) consists of two sets:

• V, a nonempty set of vertices.
• E, a set of unordered pairs of vertices called edges.
  In the graph shown,
  - The vertex set is
  V = {A, B, C, D, E}
  - The edge set is
  E = {A, B}, {A, D}, {A, E}, {B, C}, {B, D}, {C, D}, {C, E} }
  OE
  C
  A
  B
  D
• The order of a graph is |V|, the
  number of vertices.
• The size of a graph is | E|, the
  number of edges.Simple graphs, multigraphs and pseudographs

Types of Graphs

A graph containing multiple edges (edges connecting the same
vertices) is called a multigraph.
A graph containing loops (edges that connects a vertex to itself) and
perhaps multiple edges, is called a pseudograph.
A simple graph contains neither loops nor multiple edges.
.C
OD
B
A
C
+C
D
B
B
A
ADirected graphs

Directed Graphs (Digraphs)

( We won't focus on these)
A directed graph (digraph) G = (V, E)
consists of two sets:

• V, a nonempty set of vertices
• E, a set of directed edges (or arcs)
  associated with an ordered pair of
  vertices.
  The directed edge associated with (u, v)
  starts at u and ends at v.
• GBR
• FRA
• USA
  TA
• USA
  GBR
  ITA
  FRAGraph model - module dependency

Graph Models and Applications

Module Dependency Graph

A module dependency graph
provides a useful tool for
understanding how different
modules of a program
interact.
In a program dependency
graph, each module is
represented by a vertex.
There is a directed edge from
a module to a second module
if the second module depends
on the first.
main
display
parser
protocol
abstract
syntax tree
page
networkGraph model - precedence

Precedence Graph for Program Statements

Suppose we are writing a
program with the statements
shown.
How can you represent the
precedence using a graph?
Statement 1
a == 0
Statement 2
b == 1
Statement 3
c == a+1
Statement 4
d := b+a
Statement 5
e := d + 1
Statement 6
e == c+dGraph model - precedence
The dependence of statements on
previous statements can be
represented by a directed graph.
Each statement is represented by a
vertex, and there is an edge from one
statement to a second statement if the
second statement cannot be executed
before the first statement.
This resulting graph is called a
precedence graph.Graph model - airline routes

Airline Routes Graph Model

1. What is the shortest
path from one airport
to another by distance?
2. How about by flight
time?
In either case we must use
a weighted graph (not
shown), whose edges are
labeled with the distances
or times between airports.
CRP
OMA
AN
AMA
BDL
LE
MAR
DU
DE
STU
GEC
MCI
FLL
BO
B
PIT
SP
RNC
SD
SNA
LBB
STW
MH
RSW
BUR
BUF
ÒNŤ
TU
SFO
HRL
The graph shown is the undirected, unweighted
graph. We will explore weighted graphs in
detail during future lessons.
ALE
PB
PD
OKOGraphs are EVERYWHERE!

Ubiquitous Graph Applications

• Electrical/water/gas networks (connections, conductors)
• Road/railway networks (stations, lines)
• Sports tournaments (teams, matches)
• Internet (sites, links)
• Social networks (users, friends)
• Molecules (atoms, chemical bonds)
• Calendars (events, overlaps)
• Neural networks (neurons, connections)
• Tree graphs (events, probabilities)
• Concept maps (concepts, relations)
• Hierarchical structures
• Protein interactions, DNA
• Structure of a polyhedron
• .
  .
  dington
  Road
  Marylebone
  Baker
  Street
  Portland
  Street
  Euston
  1 Warren Street
  Euston
  Square
  Edgware
  Road
  Farrings
  rove
  Bayswater
  +
  Notting
  Hill Gate
  Lancaster
  Gate
  Bond
  Street
  Oxford
  Circus
  Chancer
  Lane
  Queensway
  Marble
  Arch
  + Tottenham
  Court Road
  Covent Garden t
  Green Park
  Leicester Square +
  Hyde Park Corner
  Knightsbridge
  Piccadilly
  Circus
  + Canne
  ta Charing
  Cross
  Gloucester
  Road
  St. James's
  Par
  Temple
  Earl's
  Court
  South
  Kensington
  Sloane
  Square
  Westminster
  Embankment f
  H
  H
  c
  H
  H
  Regent's Park
  Russell
  Square
  Goodge
  Street
  Land
  ark
  Holborn
  High Street
  Kensington
  Mansion Ho
  +-Blackfriars-
  VictoriaTerminology - undirected graphs

Terminology for Undirected Graphs

Consider an undirected graph G (V, E).

• Two vertices u and v are adjacent (or neighbors) in G if u and v are
  endpoints of an edge e of G. This edge e is incident with the vertices
  u and v. The edge e connects u and v.
• The set of all neighbors of a vertex v is called the neighborhood of v,
  denoted N(v).
• The degree of a vertex v is the number of edges incident with it, and
  we denote this deg(v).
  A vertex of degree 0 is isolated.
  A vertex of degree 1 is pendant.Example

Graph Degree and Neighborhood Example

A (G ) :
max des in G
8 (G) : min deg in G
Find the degrees and the neighborhoods of each vertex in the graphs
shown. Find the max and sum of the degrees in each.
4
9
b
C
d
2
3
·
0
Nbdª
f 4
e
g
Vtx
des
-
a
b
2
4
4
e
1
3
f
S
4
0
( b, f3
{a, c,e,f}
Es, die, f}
Ec3
(b,c,f3
(a, b, c,e)
¢
9
b
C
d
e
4
5
1
5
6
a
b
C
e
d
Vtx
deg
Nbd
& b, d,e3
(a, b, c, d,e)Handshaking lemma

Handshaking Lemma and Degree Sequence

Handshaking Lemma

Theorem
In a simple graph with n vertices, the maximum degree of a vertex is
n -1.
Theorem (Handshaking lemma)
Consider an undirected graph G = (V, E) with m edges. Then,
deg(v) = 2m
෍
vEVDegree sequence

Degree Sequence of a Graph

The degree sequence of a graph is the sequence of
the degrees of the vertices in decreasing order
(usually).
The degree sequences of the graphs shown are:
S1: 3,3,3,2,1
S2: 4,3,3,3,1
Example
(Simple only!)
How many edges does a graph have if its degree
sequence is s: 5,2,2,2,2,1? Draw an example.
6 vertices
{ deg(v) = 2/El =)
14 = 2/El
(order 6)
VEV
IEL = 7 (5:7 7)
1
3
3
2
3
3
4
3
3Explore

Even and Odd Degree Vertices

Consider the following graphs. How many vertices have even degrees
and how many have odd degrees?
1. a
b
e 4
od 2
3
1
1
d
f 2
e
@ 2
e 2
d 2
even :
odd :
4
1
4
3
6
0
2
2
2
b
b
c 3
2
3
ac
a
d
4 5
2
2
C
b
3
2Odd degree vertices (1/2)

Theorem on Odd Degree Vertices

Theorem
An undirected graph has an even number of vertices of odd degree.
Proof
Consider G = (U, E) where IEl =m
Let V1 = { vertices of even degree ?
V2 = { vertices of old degrees
2 m = > deg (v) =
VEV
& deg(v )
VEV,
+
& deg (v)
.
VE V2Odd degree vertices (2/2)
Since HUEV,, deg (v) is even => 1 is even
Since 1 + 2) is am, which is even .
is even.
But, all term in 2 is
odd .
So , there must be an even number of terms in
(2)
.: There is always on
Yven # of odd degree vertices.Complete graphs

Complete Graphs and Edges

Complete Graph Definition

A complete graph on n vertices, denoted Kn, is a simple graph in which
every vertex is connected to every other vertex.
The first 6 complete graphs are shown.
1. What is the degree sequence of Kn?
2. How many edges are in Kn?
K2
K3
K5
K6
des 8%!
Size :
0
1,1
2, 2, 2
K4
3,3, 3,3
0
1
3
6
10Edges in a complete graph

Number of Edges in a Complete Graph

Theorem
The number of edges in a complete graph Kn is
e =
n(n-1)
2
=
(2)
Proof
Kn has 1 vertices.
Each vtx is
adj .
to the other n-1 vertices.
So, at each vtx there are n-1 edge-ends.
=> The total # of
f edge-ends is n ( - 1 ) . But each edge has 2 ends,
vertices edge- ends
1 (1-1) = e
2Common degree

Common Degree Theorem

Theorem In any simple graph G, there are at least 2 vertices of the
same degree.
Proof Let G = (V,E) where IvI = n
G simple => S(G) = 0 and D(G) = n-1
Case 1: Ja vix or degree o.
Then , the largest possible degree is n - 2 . D ( G ) < n - 2
=) } n-1 possible degrees. (Holes)
Case 2.'
A a vtx of deg O. So 8(6)=1
Then, &(G) => ] n-l possible degrees
( Holes)
In both cases, we have A-1 values (Holos) and in vertices (pigeons)
: By the pigeonhole principle, at least 2 vertices have the same degree.Cyclic graphs

Cyclic and Regular Graphs

Cyclic Graph Definition

The cyclic graph on n vertices (where n ≥ 3) consists of:

• Vertex set V = { v1, V2, ... , Un}
• Edge set E = {{v1, 12}, {v2, 13}, ... {vn-1, Un}, {un, v1}}
  The first 4 cyclic graphs are shown.
  C3
  CA
  C5
  C6Regular graphs

Regular Graph Example

A graph is k -regular if every vertex has degree k.
Example
The graph shown is called a wheel graph (for obvious reasons).
List the degree sequence to confirm it is not regular.
Create a subgraph of W6 that is regular.
W6The utility graph

Utility Graph and Planarity

Consider the three houses shown. Each
must be connected to three utilities
(water, gas, electric).
1. Draw the corresponding utility
graph.
2. Can you draw this on paper without
any edge crossings? NolBipartite graphs

Bipartite Graphs and Coloring

Bipartite Graph Definition

A simple graph G is a bipartite graph if its vertex set V can be
partitioned into two disjoint sets V1 and V2 such that each edge in G
connects a vertex in V1 and a vertex in V2. The pair (V1, V2) is a
bipartition of the vertex set V of G.
Example
VI
V2
V2
Va
Is C6 bipartite?
V 1 = { V, V3, Vs}
VS
V6
Nu
V2 = {V2, Va, Vo}
Example
Is K3 bipartite?
V3
If we split V into a disjoint sets, one must contain
Theorem
A simple graph is bipartite if and only if it
is possible to assign one of two different
colors to each vertex of the graph so that
no two adjacent vertices are assigned the
same color.
2 vertices . If Ky were bipartite , these 2 could not be adj . But they are! contr.
Not biputin.
Vg
VExample

Bipartite Graph Identification

Are the graphs shown bipartite?
C
g
f
e
d
Yes. V .= {a,b,d} V2= {c,e,f,g3
b
a
C
e
d
No, Just consider a, b , f.Complete bipartite graphs

Complete Bipartite Graphs

A complete bipartite graph Km,n is a bipartite graph in which the
bipartition of the vertex set is (M, N) and each of the m vertices in M is
connected to each of the n vertices in N.
The utility graph is thus K3,3.
K2,3
K3,3
The graph Km,n has mn edges.
K3,5
K2,6Connected components

Connected Components in Graphs

Suppose we wanted to model the relationship between numbers that share
a divisor greater than 1. i.e., the numbers a, b such that gcd (a, b) > 1
In the graph shown, the vertex set is
2
V = {2,3,4,5,6,7}
And the edge set is
2,4}, {2,6}, {3,6}, {4,6}}
The degree sequence (in vertex order) is
2,1,2,0,3,0
3
. 7
4
6
· 5
The graph is not connected, but it has three connected components:
{2,3,4,6}, {5}, {7}