Graph Properties and Definitions pt3 ​

Here we regroup some definitions which are fundamental to get started on graph theory.

Graph Isomorphism ​

Let's consider two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$

An isomorphism is a relation $\varphi :V_1\to V_2$ between the vertices of the first graph and those of the second one

1. It must be bijective
2. $\mathrm{\forall }u,v\in V_1|(u,v)\in E_1\iff (\varphi (u),\varphi (v))\in E_2$
   1. The mapping preserves the adjacency between vertices of the same graph
   2. if $u_1,v_1$ are connected through an edge, then $u_2,v_2$ must be too

We say that " $G_1$ and $G_2$ are isomorphic", or $G_1\simeq G_2$, if there is an isomorphism between $G_1$ and $G_2$.

Here's an example:

So now, let's consider these two graphs: can we find an isomorphism?

G1              |   G2
    (1)         |       (a)-(b)-(c)
  /     \       |
(3)     (2)     |

#This is an isomorphism G1 ≃ G2!
# ϕ(1) = a
# ϕ(2) = b
# ϕ(3) = c

G1              |   G2
    (1)         |       (a)-(b)-(c)
  /     \       |
(3)     (2)     |

#This is an isomorphism G1 ≃ G2!
# ϕ(1) = a
# ϕ(2) = b
# ϕ(3) = c

Mind that there is more than one isomorphism

• To this day, it is an NP-complete problem to verify if two graphs are isomorphic. Nobody has found a solution in polynomial time.

Necessary but not sufficient conditions ​

From another point of view, it is relatively easy to find out whether two graphs $G_1,G_2$ are not isomorphic. Here are some properties that stand true but are not sufficient:

1. $|V1|=|V2|,|E1|=|E2|$ are necessary (but not sufficient) conditions
2. $\varphi (u\in V)\in V_2\to deg(u\in V)=deg(\varphi (u\in V))$
   1. The isomorphism maps vertices with the same degree
3. Degree Sequence: given $G=(V,E)$ is a sorted vector of length $n=|V|$, which means vertices are sorted based on their degrees.
   1. Two graphs are isomorphic if they have the same degree sequences, $deg-seq(G_1)=deg-seq(G_2)$ is a necessary (but not sufficient) condition
4. $CC(G_1)=CC(G_2)$
   1. Same number of connected components
5. $\omega (G_1)=\omega (G_2)$
   1. Clique number are the same

There are many properties we could list but nothing helped to solve the problem.

Cut ​

A cut is a pair $(S,V\setminus S)$, $S\subseteq V$ dividing a graph in two partitions of vertices.

• Given a graph, we can always partition it into two subsets of vertices
• Given a cut, we can point out the edges crossing it.

Cut respects A ​

Let:

• $G$ be a graph $G(V,E)$
• $A\subseteq E$ subset of edges.
• $(S,V\setminus S)$ be a cut (which partitions into two subsets the vertices of the graph $G$ )

The cut $(S,V\setminus S)$ is said to respect A, if no edges of A cross the cut.

Light edge ​

Light edge is defined with respect to a particular cut.

Light edge $(u,v)\in E$, is an edge such that:

• $(u\in S\wedge v\in V\setminus S)\vee (u\in V\setminus S\wedge v\in S)$
  • The vertices $u,v$ are not in the same subset
• $w(u,v)\le w(x,y)$
  • The edge has the minimum weight out of all the edges crossing the cut

Safe Edge ​

Let

• $A\subseteq E$ be a subset of edges, contained in some MST for $G(V,E)$.
• $(u,v)\notin A$ be an edge
  • $(u,v)\in E$.

The edge $(u,v)$ is a safe edge for $A$ if $A\cup (u,v)$ is contained in some MST too.