How can I show that for each $e = uv \in F_0$ we have $H[F^* \cup e]$ contains a cycle

76 Views Asked by At

First, I present some definitions. Let $G$ a graph. For each $Z \subseteq E(G)$, we denote the graph $G[Z]$ by the $(V(G), Z)$. Let ${\cal P}$ a partition of $V(G)$. Define the graph $G_{\cal P}$ obtained by identifyng of the vertices of each part of ${\cal P}$ (identifyng the vertices of inside of each part of ${\cal P}$). Note that $|V(G_{\cal P})| = |{\cal P}|$ and $|E(G_{\cal P})| = |E(G)|$. This is, $G_{\cal P} = (V(G_{\cal P}), E(G))$.

Let $V_s \in {\cal P}$. Define the partition ${\cal P} \div V_s$ by the $({\cal P} - V_s) \cup \{x_1,\ldots,x_k\}$ with each $x_i$ a vertice of $V_s$. The figure below ilustrate the graph $G$ with the partition ${\cal P}$ of $V(G)$, $G_{\cal P}$, ${\cal P} \div V_j$ and $G_{{\cal P} \div V_j}$.

Ilustration

Lastly, we denote by the $part(G)$ partition of $V(G)$ such that vertices pair $\{u,v\}$ belongs the same part of $part(G)$ if and only if $u$ and $v$ belongs the same connected component of $G$. For example, in the figure below we have the graph $G$ with $V(G) = \{a,b,c,d,e\}$. Therefore, $part(G) = \{V_1,V_2\}$ such that $V_1 = \{a,b,c\}$ and $V_2 = \{d,e\}$. This is, $part(G)$ has the parts $V_1$ and $V_2$.

Example of part(G).

I wish show the following:

Let $H = (V,F' \cup F)$ be a graph such that $H[F]$ is a forest. Let $F_0,F_1,....,F_k$ disjoint edge subsets of $F$(this is $F_i \cap F_j = \emptyset$ and $F_i \subseteq F$) and $F_1',...,F_k'$ be disjoint edge subsets of $F'$(this is $F_i'\cap F_j' = \emptyset$ and $F_i'\subseteq F'$). Let $F_0 = \{e_1,...,e_k\}$. Let ${\cal P} = part(H[F_0])$. If for each $i \in \{1,...,k\}$ the following conditions are true:

1.$|F_i'| = |F_i| + 1$;

2.$part(H_{\cal P}[F_i']) = part(H_{\cal P}[F_i])$;

3.Let $e_i = u_i v_i$ (note that $e_i$ are the edges of $F_0$). Se $u_i$ and $v_i$ belongs $V_j \in {\cal P}$, then $H_{{\cal P}\div V_j}[F_i']$ is a forest such that exists only a path from $u_i$ to $v_i$ in $H_{{\cal P} \div V_j}[F_i']$.(This is,not exists other vertices pair $u,v$ in $V_j$ such that $u$ and $v$ are connected in $H_{{\cal P} \div V_j}[F_i']$).

Let $F^* = (F-F_0-\bigcup_{i=1}^{k}F_i) \cup \bigcup_{i=1}^{k}F_i'$. How to prove that for each edge $e = uv \in F_0$, we have that $F^* \cup e$ (this is, $u$ and $v$ are connected in $H[F^*]$). Follows the reasonig:

Suppose by contradiction, that exists a edge $e_i = u_i v_i \in F_0$ such that $u_i$ and $v_i$ are not connected in $H[F^*]$. Let $V_s$ the part of ${\cal P}$ that contain $u_i$ and $v_i$. By the property (c), we have that exists a path from $u_i$ to $v_i$ in the graph $H_{\cal P \div V_s}[F_i']$. Therefore, exists the vertices $x$ and $y$ in some $V_t \in {\cal P}$ such that $x$ and $y$ are not connected in $H[F^*]$. The figure below illustrate this:

figure

How can I find a contradiction?

Since $H[F]$ is a forest, then $H_{\cal P}[F-F_0]$ is a forest. This help?

I thinking in to use property (b) and (c) and the fact $H_{\cal P}[F-F_0]$ is a forest. This help?

Any other ideas to show this are welcome too.