length of common cycle in two k-connected subgraphs of a graph

156 Views Asked by At

In a given graph $G$, $G_1$ and $G_2$ are maximal k-connected subgraphs, I have to prove that the length of the common cycle is atmost $K$ i.e. they have atmost $k-1$ common nodes.

I am unsure on how to get started in the proof, any help and related links are appreciated.

2

There are 2 best solutions below

0
On

I would try proving this by contradiction. Suppose $V(G_1)\cap V(G_2) \geq k$. Then I would show that $G_1\cup G_2$ is $k$-connected. This would contradict the maximality of $G_1$ and $G_2$. I would look at the proof that any two distinct blocks in a graph contain at most one common vertex for some more help.

0
On

Well, first of all you mean two maximal $k$-connected subgraphs $G_1$ and $G_2$; as in $G_1$ and $G_2$ are $k$-connected but there is no subgraph $G'_1 \supset G_1$ of $G_1$ nor is there a subgraph $G'_2 \supset G_2$ of $G_2$ that is $k$-connected.

The result you want is Claim 1 below:

Claim 1: Suppose that $G_1$ and $G_2$ share $k$ or more vertices. Then $G_1 \cup G_2$ is $k$-connected, which contradicts that $G_1$ and $G_2$ are maximal $k$-connected graphs.

Indeed, we show that $G_1 \cup G_2$ is still connected even after removing any set $S$ of $k-1$ vertices if $G_1$ and $G_2$ intersect on a set $U$ of $k$ or more vertices. Indeed, let $S$ be any set of $k-1$ vertices of $G_1 \cup G_2$. Then $G_1 \setminus S$ is still connected and $G_2 \setminus S$ is still connected [why is this]. And so for any vertex $w$ in $U \setminus S$ then there is a path in $G_1 \setminus S$ from $w$ to any vertex in $G_1 \setminus S$, and there is a path in $G_2 \setminus S$ from $w$ to any vertex in $G_2 \setminus S$, so $(G_1 \cup G_2) \setminus S$ is still connected [make sure you see why]. Thus indeed $G_1 \cup G_2$ is still connected even after removing any set $S$ of $k-1$ vertices if $G_1$ and $G_2$ intersect on a set $U$ of $k$ or more vertices.