Week 1 Graphs, isomorphisms and invariants

Question 1

Graph - adjacency matrix version

Answer 1

A graph is a square symmetric non-negative integer matrix

Question 2

Isomorphism - adjacency matrix version

Answer 2

Two graphs (adjacency matrices) A and B are isomorphic if
there exists a permutation matrix P satisfying B= P−1AP.

Question 3

Graph - set theoretic version

Answer 3

A graph is a triple (V,E,ε) consisting of a set V (of
vertices), a set E (of edges) and a function
ε: E →P1(V) ∪P2(V) (called the endpoint map).

Question 4

Isomorphism - set theoretic version

Answer 4

We say that graphs G= (V,E,ε) and G′= (V′,E′,ε′) are
isomorphic if there exists a pair of bijective functions
ϕ: V →V′and ψ: E →E′satisfying
ε′◦ψ= ϕ∗◦ε.