Graph theory
Bipartite characterization, representation of graphs, graph isomorphism
Lecture 16 Mar 14 2018
Topics covered
I Eulerian graphs and a characterization
I Characterization of bipartite graphs using odd cycles.
Today
I Graph representation as a matrix.
I Comparing graphs: isomorphism
Definition
A graph is calledbipartite, if the vertices of the graph can be partitioned intoV =X∪Y,X∩Y =∅ s.t., ∀e= (u, v)∈E,
I either u∈X and v∈Y
I orv∈X and u∈Y
Example: m jobs andnpeople, kcourses and `students.
I How can we check if a graph is bipartite?
I Can we characterize bipartite graphs?
Recall: A path or a cycle has length nif the number of edges in it is n.
I A path (or cycle) is call odd/even if its length is odd/even.
Lemma
Every closed odd walkcontains an odd cycle.
Proof: By induction on the length of the given closed odd walk.
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I ( =⇒) direction is easy.
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I ( =⇒) direction is easy.
I Let Gbe bipartite with (V =X∪Y). Then, every walk in G alternates betweenX, Y.
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I ( =⇒) direction is easy.
I Let Gbe bipartite with (V =X∪Y). Then, every walk in G alternates betweenX, Y.
=⇒ if we start fromX, each return to X can only happen after an even number of steps.
=⇒ G has no odd cycles.
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I (⇐=) Suppose Ghas no odd cycle, then let us construct the bipartition. Wlog assumeG is connected.
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I (⇐=) Suppose Ghas no odd cycle, then let us construct the bipartition. Wlog assumeG is connected.
I Let u∈V. BreakV into
X ={v∈V | length of shortest pathPuv fromuto vis even}, Y ={v∈V | length of shortest pathPuv fromuto vis odd},
Lemma
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I (⇐=) Suppose Ghas no odd cycle, then let us construct the bipartition. Wlog assumeG is connected.
I Let u∈V. BreakV into
X ={v∈V | length of shortest pathPuv fromuto vis even}, Y ={v∈V | length of shortest pathPuv fromuto vis odd},
I If there is an edge vv0 between two vertices ofX or two vertices of Y, this creates a closed odd walk: uPuvvv0Pv0uu.
Every closed odd walkcontains an odd cycle.
Theorem, Konig, 1936
A graph is bipartite iff it has no odd cycle.
Proof:
I (⇐=) Suppose Ghas no odd cycle, then let us construct the bipartition. Wlog assumeG is connected.
I Let u∈V. BreakV into
X ={v∈V | length of shortest pathPuv fromuto vis even}, Y ={v∈V | length of shortest pathPuv fromuto vis odd},
I If there is an edge vv0 between two vertices ofX or two vertices of Y, this creates a closed odd walk: uPuvvv0Pv0uu.
I By Lemma, it must contain an odd cycle: contradiction.
I This along with X∩Y =∅ andX∪Y =V, impliesX, Y is a bipartition.
To represent it, we need to name the vertices...
v1
v2 v3
v4
To represent it, we need to name the vertices...
I As an adjacency list:
v1 v2, v4
v2 v1, v3
v3 v2, v4
v4 v1, v3
v1
v2 v3
v4
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
v1
v2 v3
v4
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
I But we want to study properties that are independent of the naming, e.g., connectivity.
I Are two given graphs the “same”, wrt these properties?
v1
v2 v3
v4a
b c
d
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
I But we want to study properties that are independent of the naming, e.g., connectivity.
I Are two given graphs the “same”, wrt these properties?
v1
v2 v3
v4a
b c
d
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
a b c d a 0 0 1 1 b 0 0 1 1 c 1 1 0 0 d 1 1 0 0
I But we want to study properties that are independent of the naming, e.g., connectivity.
I Are two given graphs the “same”, wrt these properties?
v1
v2 v3
v4a
b c
d
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
v1 v3 v2 v4
v1 0 0 1 1
v3 0 0 1 1
v2 1 1 0 0
v4 1 1 0 0
a b c d a 0 0 1 1 b 0 0 1 1 c 1 1 0 0 d 1 1 0 0
I But we want to study properties that are independent of the naming, e.g., connectivity.
I Are two given graphs the “same”, wrt these properties?
v1
v2 v3
v4a
b c
d
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
v1 v3 v2 v4
v1 0 0 1 1
v3 0 0 1 1
v2 1 1 0 0
v4 1 1 0 0
a b c d a 0 0 1 1 b 0 0 1 1 c 1 1 0 0 d 1 1 0 0
I Reordering of vertices is same as applying apermutationto rows and colums of A(G).
I So, it seems two graphs are “same” if by reordering and renaming the vertices we get the same graph/matrix.
v1
v2 v3
v4a
b c
d
To represent it, we need to name the vertices...
I As an adjacency matrix:
v1 v2 v3 v4
v1 0 1 0 1
v2 1 0 1 0
v3 0 1 0 1
v4 1 0 1 0
v1 v3 v2 v4
v1 0 0 1 1
v3 0 0 1 1
v2 1 1 0 0
v4 1 1 0 0
a b c d a 0 0 1 1 b 0 0 1 1 c 1 1 0 0 d 1 1 0 0
I Reordering of vertices is same as applying apermutationto rows and colums of A(G).
I So, it seems two graphs are “same” if by reordering and renaming the vertices we get the same graph/matrix.
I How do we formalize this?
Isomorphism
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
reordering/renaming.
I What are the properties of this function/relation: R={(G, H)| ∃ an isomorphism fromGtoH}.
Proposition
The isomorphism relation is an equivalence relation.
I The equivalence classes are called isomorphism classes.
I When we talked about an “unlabeled” graph till now, we actually meant the isomorphism class of that graph!
Isomorphism
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
I Thus, it is a bijection that “preserves” the edge relation.
I Can be checked using adjacency matrix by reordering/renaming.
I What are the properties of this function/relation:
R={(G, H)| ∃ an isomorphism fromGtoH}.
I The equivalence classes are called isomorphism classes.
I When we talked about an “unlabeled” graph till now, we actually meant the isomorphism class of that graph!
Isomorphism
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
I Thus, it is a bijection that “preserves” the edge relation.
I Can be checked using adjacency matrix by reordering/renaming.
I What are the properties of this function/relation:
R={(G, H)| ∃ an isomorphism fromGtoH}.
Proposition
The isomorphism relation is an equivalence relation.
actually meant the isomorphism class of that graph!
Isomorphism
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
I Thus, it is a bijection that “preserves” the edge relation.
I Can be checked using adjacency matrix by reordering/renaming.
I What are the properties of this function/relation:
R={(G, H)| ∃ an isomorphism fromGtoH}.
Proposition
The isomorphism relation is an equivalence relation.
I The equivalence classes are called isomorphism classes.
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
I Thus, it is a bijection that “preserves” the edge relation.
I Can be checked using adjacency matrix by reordering/renaming.
I What are the properties of this function/relation:
R={(G, H)| ∃ an isomorphism fromGtoH}.
Proposition
The isomorphism relation is an equivalence relation.
I The equivalence classes are called isomorphism classes.
I When we talked about an “unlabeled” graph till now, we actually meant the isomorphism class of that graph!
Graph isomorphism
3. check that it preserves the adjacency relation
I To show that two graphs arenon-isomorphic, find a structural property that is different.
I To show that two graphs are isomorphic, you have to 1. give names to vertices
2. specify a bijection
3. check that it preserves the adjacency relation
I To show that two graphs arenon-isomorphic, find a structural property that is different.
Is checking graph isomorphism easy?
I Qn: Which of these graphs are isomorphic?
I vertices are 2-element subsets of 5-element set and edges are pairs of disjoint 2-element subsets.
I 2 vertices that do not share an edge, have exactly 1 common nbr.
Further reading: Graph and sub-graph isomorphism problems.
Is checking graph isomorphism easy?
I Qn: Which of these graphs are isomorphic?
I A: All of them!
pairs of disjoint 2-element subsets.
I 2 vertices that do not share an edge, have exactly 1 common nbr.
Further reading: Graph and sub-graph isomorphism problems.
Is checking graph isomorphism easy?
I Qn: Which of these graphs are isomorphic?
I A: All of them!
I This graph is called the Petersen graph and has some very interesting propreties.
common nbr.
Further reading: Graph and sub-graph isomorphism problems.
Is checking graph isomorphism easy?
I Qn: Which of these graphs are isomorphic?
I A: All of them!
I This graph is called the Petersen graph and has some very interesting propreties.
I vertices are 2-element subsets of 5-element set and edges are pairs of disjoint 2-element subsets.
Further reading: Graph and sub-graph isomorphism problems.
Is checking graph isomorphism easy?
I Qn: Which of these graphs are isomorphic?
I A: All of them!
I This graph is called the Petersen graph and has some very interesting propreties.
I vertices are 2-element subsets of 5-element set and edges are pairs of disjoint 2-element subsets.
I 2 vertices that do not share an edge, have exactly 1 common nbr.
I Qn: Which of these graphs are isomorphic?
I A: All of them!
I This graph is called the Petersen graph and has some very interesting propreties.
I vertices are 2-element subsets of 5-element set and edges are pairs of disjoint 2-element subsets.
I 2 vertices that do not share an edge, have exactly 1 common nbr.
Further reading: Graph and sub-graph isomorphism problems.
Some special graphs and notations
I Complete graphs Kn
I Complete bipartite graphs Ki,j
I PathsPn I Cycles Cn
Figure:A whole graph zoo!
properties, i.e., properties that do not depend on the naming of vertices are preserved.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
I Are C5 and P5∪ {e} isomorphic?
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
3. G,H have the same # vertices of degree k,∀k∈N.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
3. G,H have the same # vertices of degree k,∀k∈N.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
3. G,H have the same # vertices of degree k,∀k∈N.
4. Ghask paths/cycles of lengthr iffH hask paths/cycles of lengthr.
properties, i.e., properties that do not depend on the naming of vertices are preserved.
Theorem
IfGis isomorphic to H, then the following properties are preserved:
1. G,H have same # vertices.
2. G,H have same # edges.
3. G,H have the same # vertices of degree k,∀k∈N.
4. Ghask paths/cycles of lengthr iffH hask paths/cycles of lengthr.
5. G is bipartite iffH is bipartite.
6. . . .
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
What ifG=H?
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
What ifG=H?
Definition
AnautomorphismofGis an isomorphism fromGto itself, i.e. a bijectionf :V(G)→V(G) s.t. uv ∈E(G) ifff(u)f(v)∈E(G).
Definition
Anisomorphism from simple graphGtoH is abijection f :V(G)→V(H) such thatuv∈E(G) ifff(u)f(v)∈E(H).
What ifG=H?
Definition
AnautomorphismofGis an isomorphism fromGto itself, i.e. a bijectionf :V(G)→V(G) s.t. uv ∈E(G) ifff(u)f(v)∈E(G).
I What are the automorphisms of P4?
Definition
AnautomorphismofGis an isomorphism fromGto itself, i.e. a bijectionf :V(G)→V(G) s.t. uv ∈E(G) ifff(u)f(v)∈E(G).
I What are the automorphisms of P4?
I How many automorphisms does Kn have?
Definition
AnautomorphismofGis an isomorphism fromGto itself, i.e. a bijectionf :V(G)→V(G) s.t. uv ∈E(G) ifff(u)f(v)∈E(G).
I What are the automorphisms of P4?
I How many automorphisms does Kn have?
I How many automorphisms does Kr,s have?
Practical applications in graph drawing, visualization, molecular symmetry, structured boolean satisfiability, formal verification, linear programming...
Practical applications in graph drawing, visualization, molecular symmetry, structured boolean satisfiability, formal verification, linear programming...
