Will the proof become a spoof, if we replace'G is a simple graph' by ' G is a loopless graph'?

Question

Will the proof hold, if we stricter the condition on simple graph? If we replace simple graph by loopless graph[graph without loop, it can have multiple edges or parallel edges]. Will the proof hold for this theorem? I don't see any wrong in the proof? Will the proof become spoof?

Answer 1

You're right that the proof still holds.

If it reassures you, we can prove that parallel edges can't possibly matter to the inequality $\kappa(G) \le \kappa'(G)$. If $G$ is a graph with parallel edges, and we let $H$ be its "simplification" (deleting all but one copy of every parallel edge), then:

• $\kappa'(H) \le \kappa'(G)$, since every edge cut in $G$ remains an edge cut in $H$ but possibly has fewer edges in it now.
• $\kappa(G) = \kappa(H)$, since any set of vertices induces a connected subgraph of $G$ if and only if it induces a connected subgraph of $H$.

If we've shown the inequality for simple graphs, then $\kappa(H) \le \kappa'(H)$, and therefore $\kappa(G) \le \kappa'(G)$.

For that matter, loops will not affect $\kappa$ or $\kappa'$, and can only increase the minimum degree $\delta$. So the theorem holds for all kinds of multigraphs.

There's one caveat to all this. The inequality $\kappa(G) \le n(G) -1$, which we used in the proof, holds by convention, in a sense: we have $\kappa(G) \le n(G)-2$ for graphs that are not complete graphs, and we define $\kappa(K_n) = n-1$ even though there is no vertex cut of $K_n$. So if we want to deal with multigraphs, we had better define $\kappa(G) = n(G)-1$ when the simplification of $G$ is a complete graph, as well.