0
$\begingroup$

Full question: Prove that if $G$ is loopless, has no isolated vertices, has at least $2$ edges and is not $2$-connected then there exists a pair of edges $\{e_1, e_2\}$ in $G$ such that no cycle contains both $e_1$ and $e_2$.

So far I have that $G$ is not $2$-connected $\therefore$ must contain proper separations of order $0$ or order $1$. If $G$ contains only proper separations of order $1$ then $G$ is connected. If $G$ contains a proper separation of order $0$ then $G$ is disconnected. Then I have carried on from there. However the proof ends up quite verbose so I was wondering if there was a more simple way to do it.

$\endgroup$
0
$\begingroup$

If $G$ is not connected then let $e_1$ be an edge in one component $C_1$ of $G$ and let $e_2$ be an edge in another component $C_2$ of $G$. Then clearly there is no cycle containing both $e_1$ and $e_2$.

Let us assume now that $G$ is connected but not 2-connected. Then let $w$ be such that $G \setminus \{w\}$ is not a connected graph. Then let $C_1$ be one component of $G \setminus \{w\}$ and let $C_2$ be another. Then as $G$ is connected, there is an edge $e_1=wu_1$ incident to $w$ such that $u_1 \in C_1$, and there is an edge $e_2=wu_2$ incident to $w$ such that $u_2 \in C_2$. Then as every path in $G$ from $u_1$ to $u_2$ contains $w$ [because $u_1$ and $u_2$ are in different components of $G \setminus \{w\}$, it follows that there is no cycle containing both $u_1$ and $u_2$, and thus no cycle containing both $e_1$ and $e_2$.


The converse is true too. We show the following: If $G$ is 2-connected then for every pair $e_1$ and $e_2$ of edges there is a cycle $C$ containing both $e_1$ and $e_2$. Let us write $e_1=y_1y'_1$ and $e_2=y_2y'_2$.

  1. First let us assume $y'_2 \not \in \{y_1,y'_1\}$. Then we claim that there is a cycle $\hat{C}'$ in $G$ that contains both $y'_2$ and $e_1$. [Indeed Menger's Theorem says that there is a cycle $C'$ that contains $y_1$ and $y'_2$. If $C'$ contains $y'_1$ as well then this implies a claimed cycle $\hat{C}'$ containing the edge $e_1=y_1y'_1$, and $y'_2$. [Check this for yourself, draw out $C'$ containing $y_1,y'_1,y'_2$ and from this draw out the claimed cycle $\hat{C}'$.] So assume that $C'$ does not contain $y'_1$. Then let $P'$ be a path from $y'_1$ to $y'_2$ that does not contain $y_1$. Can you put $C'$ and $P'$ together to get $\hat{C}'$? If you aren't seeing this right away, it may be helpful to draw $C'$ and then the edge $e_1=y_1y'_1$ assuming $e_1=y_1y'_1 \not \in C'$, and then to draw $P'$ out from $y'_1$ to $y'_2$, stopping your pencil when $P'$ hits a vertex in $C'$.]

  2. There is a cycle $C$ that contains $e_1=y_1y'_1$ and $e_2=y_2y'_2$. [Indeed, if $\hat{C}'$ as in 1. above contains $y_2$ as well then we are done. [Indeed, draw $\hat{C}'$ out with the edge $e_1=y_1y'_1 \in \hat{C}$ and the vertices $y_2,y'_2 \in \hat{C}'$ and from this, see if you can find a cycle $C$ containing both $e_1=y_1y'_1$ and the edge $e_2=y_2y'_2$.] Otherwise, $y_2$ is not in $\hat{C}'$, and so this implies of course that $y_2 \not \in \{y_1,y'_1\}$. So now let $P''$ be a path from $y_2$ to $y_1$ that avoids $y'_2$. Can you can get the desired cycle $C$ containing both edges $e_1$ and $e_2$ from this? Draw out $\hat{C}'$ containing $e_1=y_1y'_1$ and $y'_2$ but not $y_2$, and then the edge $e_2=y_2y'_2$, and then draw the path $P''$ from $y_2$ to $y_1$, where $P"$ avoids $y'_2$, keeping in mind that $P''$ may hit another vertex in $\hat{C}'$.]

The cycle $C$ as in 2. is the desired cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy