GSanmi's blog

Graph TheoryTeoría de Grafos

Simple (undirected) Graphs

Introduction to graph theory.

German Sanmi en

0. Index

  1. Introduction
    • 1.1. Formal definition and main concepts
      • 1.1.1. Definition
      • 1.1.2. Main notions
  2. Tree characterization
    • 2.1. Leaves (leaf lemma)
    • 2.2. Equivalent statements of trees
    • 2.3. Handshaking lemma for trees
  3. Eulerian and Hamiltonian graphs
    • 3.1. Eulerian graphs
      • 3.1.1. Eulerian parity characterization
      • 3.1.2. Semieulerian characterization
    • 3.2. Hamiltonian graphs
      • 3.2.1. Main notions and definitions
      • 3.2.2. Implications (NOT Characterization)
      • 3.2.3. Sufficient conditions (Ore's theorem & Dirac's theorem) - 3.2.3.1. Ore's premise and some immediate results - 3.2.3.2. Bondy-Chvátal Lemma - 3.2.3.3. Ore's theorem - 3.2.3.4. Dirac's theorem
    • 3.3. Relation
  4. Graph coloring
    • 4.1. Definition
    • 4.2. Chromatic number
    • 4.3. Chromatic number of well-known graphs
      • 4.3.1. For a complete graph K_n
      • 4.3.2. For a cycle C_n
      • 4.3.3. For a bipartite graph G
    • 4.4. 2-colorability theorem

  5. Planar graphs

  6. Dual graphs

1. Introduction.

Graph Theory; is the discipline of mathematics which deals with the study of discrete relational structures and their properties. Conceptually, a graph is the minimal object that captures “pairwise relationships” between abstract entities.


1.1. Formal definition and main concepts.

1.1.1. Definition.

Formally, a graph (undirected graph) is the pair $G := (V,E)$ where:

  • $V$ is a finite non-empty set whose elements are called vertices.
  • $E \subseteq \binom{V}{2}$ and its elements are called edges.


1.1.2. Main notions.

There are several notions associated with the idea of a graph:

  • Adjacency: Two vertices $u,v \in V$ are said to be adjacent; $u \sim v \iff \Set{u,v} \in E$
  • Neighborhood: The neighborhood of $v \in V$ is the set $N(v) = \Set{u \in V : v \sim u}$
  • Degree: The number of adjacent vertices to a given one $v \in V$; $\text{deg}(v) = \vert N(v) \vert$

  • Subgraph of $G$ is any set: $H := (V_H, E_H) : V_H \subseteq V \land E_H \subseteq E \ \cap \ \binom{V_H}{2}$

  • Induced subgraph: $G[W] := (W, E \cap \binom{W}{2}): W \subseteq V$


Regarding a collection of adjacent vertices, we can talk about:

  • Walk; a finite sequence of adjacent vertices: $v_0…,v_t: v_{i-1} \sim v_i \ \forall i \leq t \in \mathbb{N}$

  • Path is a walk with all the vertices distinct: $v_0…,v_t:v_{i-1} \sim v_i \ \forall i \leq t \in \mathbb{N} \ \land \ v_i \neq v_j \ \ \forall i,j \in \mathbb{N}$

  • Cycle is a walk $v_0,…,v_{t-1},v_0$ where $v_0,…,v_{t-1}$ is a path.

  • Connected Vertices; Two vertices are said to be connected if one can reach the other through a path.


walk_path_cycle


Relative to the state of the vertex in the graph we can talk about:

  • Connected graph: Every pair of vertices are connected vertices.
  • Complete graph: Every pair of vertices are adjacent. They are notated simply as $K_n :=(V,E): \vert V \vert = n$ and satisfies: $u \sim v \ \ \forall u,v \in V$
  • Tree: A connected graph with no cycles.


2. Tree characterization.

Let's consider a tree $T:=(V,E)$:


tree


2.1. Leaves (leaf lemma).

“Leaf lemma” refers to a basic fact in graph theory about trees. A tree is “all branches, no cycles”. If it has at least one edge, you can’t keep walking forever without either repeating a vertex (which would create a cycle) or getting stuck. The “stuck points” at the ends are leaves, and you must have at least two ends.

We define as $L := \Set{v \in V : \vert N(v) \vert = 1}$ the set of the leaves of $T$, then:

\[\vert V \vert \geq 2 \implies \vert L \vert \geq 2\]

Basically the statement says that in any tree there are at least 2 leaves.

Let's reason by the longest path. Be $T:=(V,E) : \vert V \vert \geq 2$ a tree; since $T$ is connected we can consider for $l,t \in V$ the path between them, so let's consider by convenience the longest path in $T$, $P_{lt}:=v_0,…,v_k$.

Now consider $v_0$ (we could reason the same way for $v_k$), and let's suppose that $\vert N(v_0) \vert \geq 2$; if it is, then we can consider some $u \in V : u \sim v_0 \land u \neq v_1$, then:

  • If $u \in P \implies C_u:= u,…,v_0,v_1,u \subset T$ contradicting the acyclicity property.
  • If $u \notin P$, then $P' = u,v_0,…,v_k$ would be the longest path contradicting the maximality assumption of $P$.

So $deg(v_0) = deg(v_k) = 1$ and both are leaves in $T$.


2.2. Equivalent statements of trees.

The following statements are equivalent for a tree $T:=(V,E)$

  1. $T$ is connected and $\vert E \vert = \vert V \vert - 1$

    First, $T$ is connected by definition. Let's reason by induction.

    • $n = 2$: Consider $T:= (V,E) : V :=\Set{u,v}$. Since $T$ is connected, $u,v \in V$ are connected and thus adjacent; $u \sim v \implies E := \Set{\Set{u,v}} \implies \vert E \vert = 1 = \vert V \vert - 1$


    • Considered true for some $n$, then $T'$ is a tree verifying $\vert V' \vert = n + 1$

      Consider a leaf $t \in V' : \vert N(t) \vert = 1$ (by the leaf lemma, we can ensure its existence) and the induced graph:

      \[T:= (V,E) : \begin{cases} V = V' \setminus \Set{t} \\ E= E' \cap \binom{V' \setminus \Set{t}}{2}\end{cases}\]

      Observe that since $t$ is a leaf, then it is an endpoint for some path in $T$ and removing it does not break connectivity.

      Thus $T$ is a graph with $n$ vertices and, by $T'$ and the leaf lemma, still connected and acyclic, meaning it remains a tree. Thus $T,T'$ are two trees verifying: $\vert E \vert = n - 1 \land V' = V \cup \Set{t}$

      Let's also observe that:

      \(E= E' \cap \binom{V' \setminus \Set{t}}{2} = E' \setminus \Set{\Set{l,t} \in E' : l \in V'}\) Thus, we have:

      \[\vert E' \vert = \vert E\vert + \vert \Set{\Set{l,t} \in E': l \in V'} \vert = (n - 1) + 1 = \vert V' \vert-1\]


  2. $T$ is acyclic and $\vert E \vert = \vert V \vert - 1$. Is immediate from above.


  3. Between any two vertices there is a unique path. Reasoning by contradiction, if between $l,t \in V$ there would exist more than one path, let's say: $t,u_0,…,u_{k-1},l$ and $l,v_0,…,v_{k-1},t$, then $t,u_0,…,u_{k-1},l,v_0,…,v_k{-1},t$ would be a cycle contradicting acyclicity in trees.


  4. $T$ is minimally connected: removing any edge disconnects it.

    Observe that this stems from the uniqueness of the path for any pair of vertices. Meaning that, if $e=\Set{u,v} \in E$, then there exists a unique path $P = t,…,u,v,…l$ in $T$ and removing $e$ from $E$ leaves no path between $u$ and $v$, contradicting the connectedness premise on $T$ as a tree.


  5. $T$ is maximally acyclic: adding any missing edge creates a cycle.

    Let's consider $u,v \in V : u \ \cancel{\sim} \ v$, then, since $T$ is connected, there exists a path $u,…,v \in T$ and forcing $\Set{u,v} \in E \implies C_u = u,…v,u \subset T$ contradicting acyclicity.


2.3. Handshaking lemma for trees.

The handshaking lemma states:

\[\sum_{v \in V} deg(v) = 2 \vert E \vert\]

Let's see that we can prove this by induction:

  • Consider: $\vert V \vert = 2 \implies \displaystyle\sum_{v \in V} deg(v) = 2 = 2 \vert E \vert$

  • Consider now $\vert V \vert = n+1$, then we can consider by the leaf lemma $t \in V: deg(t) =1$:

    \[T' :=(V',E'): \begin{cases} V' = V \setminus \set{t} \\ E' = E \cap \binom{V'}{2}\end{cases}\]

    Let's observe that $T'$ is a tree with $n$ vertices, then, by the induction premise $\displaystyle\sum_{v \in V'} deg(v) = 2 \vert E' \vert$, and also, being $u \in V : u \sim t$, then $E = E' \cup \Set{u,t}$ meaning that:

    \[\sum_{v \in V} deg(v) = \sum_{v \in V'} deg(v) + 2 = 2 \vert E' \vert + 2 = 2(\vert E' \vert + 1) = 2\vert E \vert\]


Observe that this also means that there is an even number of odd-degrees.


3. Eulerian and Hamiltonian graphs.

Eulerian graphs are a class of graphs that can be traversed using each edge exactly once. Hamiltonian graphs are a class of graphs that can be traversed using each vertex exactly once.


3.1. Eulerian graphs.

Main notions and definitions

Be $G:=(V,E)$ a graph, then we define the following terms:

  • Euler walk, is a walk that goes through every edge of $E$ exactly once.
  • Euler circuit, is an eulerian walk that starts and ends at the same vertex.

Then,

  • $G$ is said to be semi-eulerian if it admits an eulerian trail but not an eulerian circuit.
  • $G$ is said to be eulerian if it admits an eulerian circuit.


3.1.1. Eulerian parity characterization.

Being $G$ a connected graph, then:

\[G \text{ is eulerian } \iff deg(v) \vert 2 \ \ \ \forall v \in V\]


First, let's see that if $G$:

  • $G \text{ is eulerian } \implies deg(v) \vert 2 \ \ \ \forall v \in V$

    If we consider $G:=(V,E)$ connected that admits an eulerian circuit, then we can think of a walk that traverses every edge without repeating any of them.

    Thus, for the walk not to repeat edges and to end in the same vertex it started, for every vertex $v \in V$ which is not the start of the walk there are at least two edges; one that enters $\Set{u,v}$ and another that gets out from $\Set{v,w}$, for every time the walk visits a vertex in $V$ (this also applies whenever the vertex gets repeated in the walk).

    Also, if $r \in V$ is the root vertex from which the walk starts, then if this vertex gets visited more than once the rule above applies, and it also has the first edge from which the walk starts and the last edge of the walk that ends returning to $r$.

    So any $v \in V$ is adjacent to an even number of vertices and thus $deg(v) \vert 2$.


  • $ deg(v) \vert 2 \ \ \ \forall v \in V \implies G \text{ admits an eulerian circuit}$

    Let's observe that we can consider a connected subgraph $G'$ so we can assume without ambiguity that $G$ is connected.

    Then, if $G$ is connected and each $v \in V$ verifies $deg(v)\vert 2$, let's see that if we consider a path $P_r$ starting in $r \in V$, then since $deg(v) \vert 2 \ \ \forall v \in V$ there are no leaves and we can't get stuck at any point and can always go through a non-traversed edge until we reach the same starting point $r$. This means that we can consider the cycle $C_r = P_r,r$ of no repeated edges. If $C_r$ goes through every edge in $E$, then it is an eulerian circuit; if not, there are still edges which have not been traversed.

    Let's suppose there are leaf edges; again, since $G$ is connected then at least one vertex of the cycle is included in a non-traversed edge. Let this vertex be $r$ again (since a cycle can be looped on any point, we can make this assumption without losing generality), then $r$ is connected to another vertex $t$ (which can be in the cycle or not) through a non-traversed edge $\Set{r,t}$; since $deg(t) \vert 2$, then we can ensure the existence of another non-traversed edge in which $t$ is included $\Set{t,l}$ (if not, by the logic described above, $deg(t)$ would be odd). Let's see that applying the same logic as in the first cycle, this circuit eventually ends up in $r$, forming another cycle of non-traversed edges that can be continued from the first cycle in an eulerian circuit.

    cycle1

    This way, reaching this point, if no more non-traversed edges remain, then we would be finished; if not, then we can repeat the same steps into another cycle.

    The point is to understand that, whenever there exists a vertex involved in a non-traversed edge, by the features of the graph, this edge goes on in a path with other non-traversed edges that eventually ends up again in the same starting vertex; thus our eulerian circuit is a walk that goes through a main cycle and completes subcycles when the accesses to these ones are presented.

    EulerianCircuit

    In the example above, we would start our walk in $r$, then $e:=r,c_2,t$ and in $t$ we enter a subcycle $C_t:=t,l,c_7,r,t$, thus $e:=r,c_2,C_t$.

    Now we continue our walk through the main cycle until we reach $c_4$ in which we get another subcycle: $C_c:= c_4,c_{41},c_{42},c_4$, thus $e:=r,c_2,C_t,C_c$ and we finish our main cycle. Our eulerian circuit will look like:

    \[e:=r,c_2,C_t,C_c,l,c_6,c_7,c_8,r\]

    Thus these conditions are sufficient to ensure the existence of an eulerian circuit.


3.1.2. Semieulerian characterization.

Now, taking $G:=(V,E)$ as a connected graph:

\[G \text{ is semi-eulerian } \iff \vert \{x \in V : \deg(x)\ \text{odd}\} \vert = 2\]

  • Let's see first that $ \vert {x \in V : \deg(x)\ \text{odd}} \vert = 2 \implies G \text{ is semi-eulerian }$

    In the terms of in/out, having two unique vertices $u,v \in V$ with an odd-degree means that these two vertices are endpoints, in the sense that you can depart from but never finish back (despite walk iterations over the same vertex), or you can get in but never get out through a non-traversed edge; any of the two cases would imply an even degree.

    Thus, let's consider $P_{uv}$, this is our main walk; if this path covers all edges in $E$, then we would be finished. If not, let's see that we already took in $P_{uv}$ the odd adjacencies, in the sense that, out of $P$, every non-traversed edge involves vertices with an even degree value like in our eulerian graph in the example above. Every non-traversed edge out of $P$, let's say $\Set{t,l}$, continues over another non-traversed edge until the starting point $t$ is met, completing a cycle.

    This in conjunction with the fact that $G$ is connected (meaning that if there are non-traversed edges by $P$ these can be reachable through $P$; at least one of those non-traversed edges involves a vertex in $P$) makes our eulerian trail a walk that goes through $P_{uv}$ from $u$, completing subcycles whenever these are presented, ending up in $v$.


  • Now, check that: $G \text{ is semi-eulerian } \implies \vert {x \in V : \deg(x)\ \text{odd}} \vert = 2$

    If $G$ is semi-eulerian, then it admits an eulerian trail. Thus, necessarily it is connected because in a single walk we can traverse all edges, meaning that all vertices are connected.

    Also, this trail starts and ends in two distinct points $u,v \in V$. These are the departure point and the arrival point, and thus these ones have odd-degrees as we said above. Also, any other vertex in $V$ has in/out edges (despite iterations over the trail) meaning that they have even degree. Thus, $\vert {x \in V : \deg(x)\ \text{odd}} \vert = 2$


3.2. Hamiltonian graphs.

3.2.1. Main notions and definitions.

Being $G:=(V,E)$ a graph. Then we have the following definitions:

  • A Hamiltonian path, $P_{H,uv}$ is a path that visits every vertex $t \in V$ exactly once.

  • A Hamiltonian cycle, $C_u$ is a cycle formed through a Hamiltonian path,$P_{H,uv}$ meaning that it visits every vertex exactly once with the exception of the starting point: $C_u := P_{H,uv},u$

We say that $G$ is Hamiltonian if it admits a hamiltonian cycle.


3.2.2. Implications (NOT Characterization).

Being $G:=(V,E)$ a hamiltonian graph, then:

  • $G$ is connected; If every single vertex is contained in a path, then for every pair of vertices there exists a path that contains those vertices so $G$ is connected.

  • $deg(v) \geq 2 \ \ \forall v \in V$. If the graph admits a hamiltonian cycle, then there exists a cycle that traverses all the vertices returning to the starting point, meaning that all vertices $v \in V$ have an in/out edge, thus it is at least two although it can be more, thus $deg(v) \geq 2$.

  • There are no "cut-vertices". Meaning that removing one vertex does not disconnect the graph, because removing a vertex causes the hamiltonian cycle to derive into a hamiltonian path, thus all vertices remain connected:

    hamiltonian1


3.2.3. Sufficient conditions (Ore's theorem & Dirac's theorem).

We are going to see sufficient conditions for a graph to be hamiltonian. We will expose the premise and then we will begin to derive results slowly, reaching the fundamental Bondy-Chvátal Lemma from which Ore's theorem is an easy corollary. Then Dirac's theorem is an immediate result of Ore's theorem.

3.2.3.1. Ore's premise and some immediate results.

Ore's premise says something like “if the graph is dense enough, it must be Hamiltonian”:

$H:=(V,E) : \big( \vert V \vert \geq 3 \wedge deg(u) + deg(v) \geq \vert V \vert \ \forall u,v \in V : u \not \sim v\big) \implies H \text{ is Hamiltonian}$


Let's start by seeing that $H$, as defined, is connected. Being $u,v \in V$, then consider $P_u := \Set{v \in V \vert \exists P_{uv} \subset H}$,

Observe that: $\nexists P_{uv} \text{ in } H \implies \ P_u \cap P_v = \varnothing \implies \vert P_u \cup P_v \vert = \vert P_u \vert + \vert P_v \vert \leq \vert V \vert$.

\[deg(t) + deg(l) \leq \vert P_u \vert -1 + \vert P_v \vert -1 = \vert V \vert - 2 < \vert V \vert \ \ \ \forall t \in P_u \wedge \forall l \in P_v\]

Observe that obviously $t \not \sim l$ .

This contradicts Ore's initial presumption on $H$, so $H$ is connected and we can safely think of a path for any pair of vertices in $V$.


Let's also observe that $deg(v) \geq 2 \ \ \forall v \in V$. If $H$ is a complete graph then there is nothing to prove, so let's suppose that:

\[\exists u,v \in V: u \not \sim v \wedge deg(v) =1 \implies deg(u) + deg(v) = deg(u) + 1 \geq \vert V \vert \implies deg(u) \geq \vert V \vert - 1\]

Also, since $\vert V \vert > deg(u) \wedge deg(u) \in \mathbb{N} \implies deg(u) = \vert V \vert -1$

This would mean that $N(u) = V \setminus \Set{u} \implies v \in N(u) \implies u \sim v$ contradicting the no adjacency premise. So there are no leaves in $H$.


Let's also observe that in $H$:

\[N(v) \cap N(u) \neq \varnothing \wedge \vert N(v) \cap N(u) \vert \geq 2 \ \ \forall u,v \in V: u \not \sim v\]

Note that $u \not \sim v \implies \Big(deg(v) + deg(u) = \vert N(u) \vert + \vert N(v) \vert \geq \vert V \vert \Big) \wedge \Big( N(u) \cup N(v) \subset V \setminus \Set{u,v}\Big)$

Then applying $\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert$, and $deg(u) + deg(v) \geq \vert V \vert$ is:

\[\vert V \vert -2 \geq \vert N(v) \cup N(u) \vert = \vert N(u) \vert + \vert N(v) \vert - \vert N(u) \cap N(v) \vert \geq \vert V \vert - \vert N(u) \cap N(v) \vert\]

Meaning that $\vert N(u) \cap N(v) \vert \geq 2$ necessarily. Then, $\exists t,l \in V : t,l \in N(u) \cap N(v) \ \ \forall u,v \in V: u \not \sim v$.


3.2.3.2. Bondy-Chvátal Lemma.

Being $G:=(V,E) : \vert V \vert = n \geq 3 \wedge deg(u) + deg(v) \geq n$, then we define $G + uv :=(V,E \cup \Set{u,v})$, observe that obviously: $u \sim v \text{ in } G \implies G = G +uv$.

This lemma stands that:

\[G \text{ is hamiltonian } \iff G + uv \text{ is hamiltonian }\]

Let's prove the lemma.

  • Observe quickly that $ G \text{ is hamiltonian } \implies G + uv \text{ is hamiltonian }$, since adding edges (supposing $u \not \sim v$) does not destroy cycles.

  • If $G + uv \text{ is hamiltonian }$, then if the cycle does not use $\Set{u,v}$ then $G \text{ is hamiltonian }$, thus let's suppose that the cycle does use $\Set{u,v}$.

    Consider the hamiltonian path $P_{H,uv} \subset G$ (which exists since $G + uv$ is hamiltonian and the hamiltonian cycle does use $\Set{u,v} \in E$). If we consider that $A:=\Set{i \in \Set{2,…,n}: v_i \sim u} \wedge B:=\Set{i \in \Set{1,…,n-i}: v_i \sim v}$ then, obviously $A$ and $B$ are the sets of the neighbours shifted by one relative to the other; let's observe that, as we discussed before:

    \[N(u) \cap N(v) \neq \varnothing \implies A - 1 := \Set{i-1: i \in A}\cap B \neq \varnothing \implies \exists i: u \sim v_{i-1} \wedge v_i \sim v\]

    Thus, taking a redirection of the path: $P:=u,…,v_{i-1},v,…,v_i,u$, we have our hamiltonian cycle.

    Bondy_Chvatal

    The image above aims to illustrate the result of the lemma; for simplicity, unnecessary edges have been omitted.


3.2.3.3. Ore's theorem.

Let's observe that, from the result before, Ore's premise guarantees $G \text{ is hamiltonian } \iff G + uv \text{ is hamiltonian }$, and this premise can be applied iteratively, meaning:

\[G \text{ is hamiltonian} \iff G + uv \text{ is hamiltonian}\iff (G + uv) + lt\text{ is hamiltonian} \iff \cdots \iff K_n\text{ is hamiltonian}\]

Observe we eventually reach a complete graph since $V$ is finite and so is the number of edges that can be included.


3.2.3.4. Dirac's theorem.

Let's observe that there is another direct result that can be derived from Ore's theorem. Being $G:=(V,E) : \vert V \vert = n \geq 3$, then:

\[deg(v) \geq \frac{n}{2} \ \ \forall v \in V \implies deg(v) + deg(u) \geq n \ \ \forall u,v \in V : u \not \sim v\]

Thus, we can say that:

\[deg(v) \geq \left\lceil \frac{n}{2}\right\rceil \quad \forall v \in V \implies G \text{ is Hamiltonian }\]

Being $\displaystyle\left\lceil \frac{n}{2}\right\rceil \quad := min \Set{z \in \mathbb{Z} \ \vert \ z \geq \frac{n}{2}}$


3.3. Relation.

Eulerian cares about degree parity and edge coverage; Hamiltonian cares about global structure and vertex coverage.

Eulerian existence has a clean parity characterization. Hamiltonian existence does not have a comparable local invariant characterization; deciding Hamiltonicity is $NP$-complete (even for many restricted graph families).


4. Graph coloring.

4.1. Definition.

Being, $G := (V,E)$, then a $k\text{-coloring}$ of $G$ is an application:

\[c : V \to \Set{1,...,k} : \big(c(u) \neq c(v) \ \ \ \forall \Set{u,v} \in E \big)\]


4.2. Chromatic number.

For $G$, we define its chromatic number as the minimum number for which a coloration exists:

\[\chi(G) := min\Set{k \ \vert \ \exists c : V \to \Set{1,...,k} \text{ is a } k\text{-coloring}}\]

Observe that this means that the Four Colour theorem states $\chi(G) \leq 4 \ \ \forall G$ and the 3-coloring problem asks whether $\chi(G) \leq 3$.


4.3. Chromatic number of well-known graphs.

Let's observe that:

4.3.1. For a complete graph $K_n$ (where $\vert V_K\vert = n$), is: $\chi(K_n) = n$.

  • First, let's see that $c : V_K \to \Set{1,…,n}$ is injective ($\vert V_K\vert = \vert \Set{1,…,n}\vert $) and it verifies:

    \[u \neq v \implies c(u) \neq c(v) \ \ \ \forall u,v \in V_K\]

    Also, since $K_n$ is a complete graph, $\forall u,v \in V_K : u \neq v \iff \Set{u,v} \in E_K$, thus:

    \[c(u) \neq c(v) \ \ \ \forall \Set{u,v} \in E_K\]

    And $c$ is a coloration.


  • Let's see now that $\neg (\exists i < n : c : V_K \to \Set{1,…,i} \text{ is a coloration})$.

    Simply, considering $c : V_K \to \Set{1,…,i}$ with $ i < n$, then $c$ is not injective and it verifies the pigeonhole principle:

    \[\exists u,v \in V_K : \big (u \neq v \land c(u) = c(v)\big)\]

    Again, for $\forall u,v \in K_n \ \ u \neq v \iff \Set{u,v} \in E_K$ and thus:

    \[\exists \Set{u,v} \in E_K : c(u) = c(v)\]

    And $c$ is not a coloration.


4.3.2. For a cycle $C_n$, $\chi(C_n) = 2$ if $n$ is even and $\chi(C_n) = 3$ if $n$ is odd.

First, let's define what a cycle graph is:

\[C_n := (V_C, E_C) : \begin{cases} V_C = \Set{v_0,...,v_{n-1}} \\ E_C = \Set{\Set{v_{i-1},v_i} : i \in \Set{1,...,n-1}} \cup \Set{\Set{v_{n-1},v_0}} \end{cases}\]

Let's observe that, as defined, the sequence: $v_0,…,v_{n-1}$ is a path, thus $v_0,…,v_{n-1},v_0$ is a cycle.

  • Now, consider the case $\exists m : n = 2m$, then, we define:

    \[c : V_C \to \Set{1,2} : c(v_i) = \begin{cases} 1 \ \text{ if } i \text{ is even}\\ 2 \ \text{ if } i \text{ is odd} \end{cases}\]

    It is clear that even and odd numbers alternate in a consecutive numeric sequence. So:

    \[c(v_{i-1}) \neq c(v_i) \ \ \forall v_{i-1},v_i \in v_0,...,v_{n-1} \implies c(v_{i-1}) \neq c(v_i) \ \ \forall \Set{v_{i-1},v_i} \in E_C\]

    For the same reason, if $n$ is even, then $n-1$ is odd and $c(v_{n-1}) \neq c(v_0)$, thus, in conclusion:

    \[c(u) \neq c(v) \ \ \forall \Set{u,v} \in E_C\]

    And $c$ is a $2-coloring$ of $C_n$. Obviously since $E_C \neq \varnothing$ it can't be $\chi(C_n) = 1$.


  • If $n = 2m + 1$ and we suppose the existence of a $2-coloring$, $c$ over $C_n$, then:

    \(c(u) \neq c(v) \ \ \forall \Set{u,v} \in E_C \implies c(v_{i-1}) \neq c(v_i) \ \ \forall \Set{v_{i-1},v_i} \in E_C \iff\) \(\iff c(v_{i-1}) \neq c(v_i) \ \ \forall v_{i-1},v_i \in v_0,...,v_{n-1}\)

    Or, in other words, any consecutive vertex in the path $v_0,…,v_{n-1}$ has different image under $c$.

    Thus, it is easy to see that:

    • Since in a $2-coloring$ there are only two possible image values

    • And $n-1$ is even (because $n$ is odd),

    Then $v_0$ and $v_{n-1}$ share the same image under $c$ and it is:

    \[c(v_{n-1}) = c(v_0) \land \Set{v_{n-1},v_0} \in E_C\]

    Triggering a contradiction with the $2-coloring$ requirement.

    Getting the example of $c$ provided above, it is easy to see that:

    \[c : V_c \to \Set{1,2,3} : c(v_i) = \begin{cases} 1 \ \text{ if } i \text{ is even } \land i \neq n -1\\ 2 \ \text{ if } i \text{ is odd} \\ 3 \end{cases}\]

    Is a $3-coloring$ of $C_n$.


4.3.3. For a bipartite graph $G$, $\chi(C_n) = 2$

A bipartite graph is a graph $G_B$ satisfying:

\[G_B := (V_B,E_B): \begin{cases}V_B := A \sqcup B \ \ (V = A\cup B \land A \cap B = \varnothing) \\ E_B \subset \binom{V_B}{2} : a \in A \land b \in B \ \ \forall \Set{a,b} \in E_B \end{cases}\]

Then, consider

\[c : V_B \to \Set{1,2} : c(v) =\begin{cases} 1 \ \ \text{ if } v \in A\\ 2 \ \ \text{ if } v \in B \end{cases}\]

Then:

\[\forall \Set{u,v} \in E_B \ \ \begin{cases} u \in A \Rightarrow c(u) = 1 \\ v \in B \Rightarrow c(v) = 2 \end{cases} \implies c(u) \neq c(v)\]

And $c$ is a $2-coloring$ of $G_B$. Of course, $E_B \neq \varnothing \implies \chi(G_B) \neq 1$.


4.4. 2-colorability theorem.

The 2-colorability characterization states that, being $G := (V,E)$ a graph, then:

\[\chi(G)=2 \iff G \text{ is bipartite } \iff \neg \exists\,\text{cycle } C \subseteq G : \ \vert \ C\ \vert \ \ \text{ is odd}\]

Observe that we already demonstrated that:

  • $G \text{ is bipartite } \implies \chi(G)=2$
  • $\chi(G)=2 \implies \neg \exists\,\text{cycle } C \subseteq G : \vert C\vert \ \text{ is odd}$ (since every odd cycle has 3 as a chromatic number).

  • $\chi(G)=2 \implies G \text{ is bipartite }$

    Observe that

    \[\chi(G)=2 \implies \exists c :V \to \Set{1,2} : c(u) \neq c(v) \ \ \forall \set{u,v} \in E\]

    We define:

    \[\begin{cases}A := \Set{u \in V \ \vert \ c(u) = 1} \\ B:= \Set{u \in V \ \vert \ c(u) = 2}\end{cases}\]

    In this context, since $c$ is an application we have:

    • $v \in V \Rightarrow c(v) = 1 \vee c(v) =2 \Leftrightarrow v \in A \vee v \in B \Rightarrow V = A \cup B$

    • $A \cap B = \varnothing$

    • $\forall \Set{u,v} \in E \implies c(u) \neq c(v) \implies (u \in A \land v \in B) \vee (v \in A \land u \in B)$


    Thus, $G$ verifies: \(\begin{cases}V := A \sqcup B \ \ (V = A\cup B \land A \cap B = \varnothing) \\ E \subset \binom{V}{2} : a \in A \land b \in B \ \ \forall \Set{a,b} \in E \end{cases}\)

Now, only last to demonstrate that:

  • $\neg \exists\,\text{cycle } C \subseteq G : \vert C\vert \ \text{ is odd} \implies G$ is bipartite.

    The premise can be negated in two ways:

    • First, $\neg \exists C \subseteq G : C \text{ is a cycle}$, then consider a vertex we call $r$ and: $A = \Set{u \vert dist(r,u) \text{ is even}}$ and $B = \Set{u \vert dist(r,u) \text{ is odd}}$. Then it is pretty obvious that $A \cup B$ and we impose that $A \cap B = \varnothing$; let's observe that this imposition requires no odd cycles.

      Being $C \subseteq G : C \text{ is odd}$, then, $C:=v_0,…,v_{n-1},v_0$ where $v_0,…,v_{n-1}$ is a path and $\Set{v_{n-1},v_0} \in E$. Let's say $r : dist(r,v_0) \land r \notin C$. Then, since $C$ is a cycle there are two paths to measure the distance between $r$ and $v_{n-1}$:

      \[dist(r,v_{n-1}) = dist(r,v_0) + dist(v_0,v_{n-1})\]

      Since $\Set{v_{n-1},v_0} \in E \Rightarrow dist(v_0,v_{n-1}) = 1 \Rightarrow dist(r,v_{n-1}) = 2 \text{ (even)}$, but also, since $C$ is odd, $n-1$ is even (meaning that $dist(v_0,v_{n-1})$ is even and $1 + dist(v_0,v_{n-1}) = dist(r,v_{n-1})$ is odd). So in summary: $A \cap B \neq \varnothing$


5. Planar graphs.

A planar graph is a graph that admits a graphical representation on a plane such that its edges do not cross each other. For example, the complete graph $K_3$ does admit a representation in which the edges do not cross, but $K_5$ does not.

Let be $G:=(V,E)$ a finite simple graph, then an embedding of $G$ into $\mathbb{R}^2$ is a function $\phi: G \to \mathbb{R}^2$ that:

  • $\forall u,v \in V \ \ \left(\phi(u), \phi(v) \in \mathbb{R}^2 \land u \neq v \implies \phi(u) \neq \phi(v) \right)$

  • $\forall e, f \in E \ \ \left( \phi(e) = \gamma_{e_1e_2}, \phi(f) = \gamma_{f_1f_2} \in \mathbb{R}^2 : e \neq f \implies \phi(e) \cap \phi(f) \subseteq \Set{\phi(e_1),\phi(e_2),\phi(f_1),\phi(f_2)} \right)$

Where $\gamma_{uv}$ is a simple arc (non-self-intersecting, continuous curve) from $\phi(u)$ to $\phi(v)$. $\phi$ maps the edges of $G$ ensuring that two different arcs only share endpoints as much.

Then, $G$ is said to be planar if it admits an embedding $\phi$ in $\mathbb{R}^2$ as above.


Associated with a drawing of a planar graph are the so-called faces, grouped in the set $F$; which are regions of the plane $\mathbb{R}^2$ enclosed by the planar drawing of the graph (here the unbounded outer face external to the graph is included). Euler's formula specifies that, for a connected planar graph $G:= (V,E)$, being $F$ the set of the faces of the drawn graph, then:

\[\ \vert \ V\ \vert \ - \ \vert \ E\ \vert \ + \ \vert \ F\ \vert \ = 2\]


6. Dual graphs.

Given a connected planar graph $G$, the dual graph is what you get when you turn faces into vertices in a planar embedding of $G$.

The drawing (planar embedding) cuts the plane into regions (faces), one unbounded “outside” face plus the bounded ones, then the dual $G^*$ is built by:

  • Putting one vertex inside each face of $G$.
  • For each $e \in E$ there exists one $e^* \in E^*$ crossing once $e$, connecting two faces.

Formally;

Being $G$ a connected planar graph and $\phi$ its drawing in $\mathbb{R}^2$. Then, we define the dual graph as:

\[G^*:= (V^*,E^*):\begin{cases}V^* &:= F = \Set{f : f \text{ is a face of }(G,\phi)} \\ E^* &:= \Set{\Set{f_1,f_2} \ \vert \ \exists e \in E \text{ between } f_1 \text{ and } f_2 } \subseteq \binom{V^*}{2}\end{cases}\]

It is important to understand that the dual depends on the embedding: Two different planar drawings of the same abstract planar graph can produce non-isomorphic duals. The dual is canonical only after you fix the embedding.

In this context, a map coloring is equal to coloring a dual graph. A map representation is in fact a dual graph.


Maths