Proving that distinct edge atoms of a graph are vertex-disjoint.

167 Views Asked by At

The Question

In Godsil and Royle's Algebraic Graph Theory, they prove that any two distinct edge atoms of a graph $X$ are vertex-disjoint, making the following argument, where $A$ and $B$ are such edge atoms:

So we may assume that $A\cup B$ is a proper subset of $V(X)$. Now, the previous lemma yields

$$|\partial(A\cup B)| + |\partial(A\cap B)|\le 2\kappa_1(X),$$

and, since $A\cup B\ne V(X)$ and $A\cap B\ne\emptyset$, this implies that

$$|\partial(A\cup B)| = |\partial(A\cap B)| = \kappa_1(X).$$

I don't understand why the second assertion is true, nor why it follows from $A\cup B\ne V(X)$ and $A\cap B\ne\emptyset$.

Background

I'm unsure how common their notation/definitions are, so I've included some below.

  • We let $\kappa_1(X)$ denote edge-connectivity;

  • For $S\subseteq V(X)$, we define $\partial S$ to be $\{xy\in E(X):x\in S, y\notin S\}$. That is, it is the set of edges with one end in $S$ and one end not in $S$;

  • An edge atom of $X$ is a subset $S\subseteq V(X)$ such that $|\partial S|=\kappa_1(X)$, and $|S|$ is minimal.

  • The lemma referenced states that $|\partial(A\cup B)|+|\partial(A\cap B)|\le |\partial A| + |\partial B|$ for $A,B\subseteq V(X)$.

1

There are 1 best solutions below

1
On BEST ANSWER

The second assertion follows from the first because, by Menger's Theorem, for any nonempty $S \subsetneq V(X)$, $|\partial S| \geq \kappa_1(X)$.

Here's another way to think about it. If either of $\partial (A \cup B)$ or $\partial (A \cap B)$ had size different from $\kappa_1 (X)$, then one of the two would have to be less than $\kappa_1 (X)$, which contradicts $\kappa_1 (X)$ being the edge connectivity, since neither $A \cap B$ or $A \cup B$ is $V(X)$ or empty.