2
$\begingroup$

Suppose that G has all vertices of even degree. What do we know about κ(G)? What do we know about κ'(G)?

I've drawn some pictures and my intuition is to say that κ(G) and κ'(G) are both even, but I don't know how to justify. I know vertex connectivity and edge-connectivity are different, but in my examples on even-degree graphs it seems like they're both even and in fact equal.

I was looking at the a square graph (4 vertices all with degree 2) and $K_5$ the complete graph on 5 vertices where all degrees are 4.

I also looked at some graphs where the degrees were different, but still even and it seemed connectivity was still even as well.

Since all vertices have an even degree, that means the minimum degree is 2 (I'm ignoring 0 since I don't think the question cares about isolated vertices). Then this means every vertex is part of a cycle. I don't know how much this helps, but it means I can't remove 1 vertex and disconnect the graph.

$\endgroup$
2
  • $\begingroup$ I have few ideas which may be useful to construct counterexamples. Let $G$ be any graph. Then graph $G^*$ is obtained from $G$ by adding a new vertex $*$ adjacent to all vertices of $G$ of odd degree and a graph $G^\diamond$ is obtained from $G$ by splitting each its edge $e=(v_1,v_2)$ into for edges $(v_1, v_e)$, $(v_1, v’_e)$, $(v_2, v_e)$, $(v_2, v’_e)$ (so we also add two new vertices $v_e$ and $v’_e$ for eachedge $e$). $\endgroup$ Nov 2 '17 at 17:42
  • $\begingroup$ I realized the Bowtie graph is a counterexample because vertex connectivity is odd (remove the middle vertex) but all degrees are even. But I still think edge connectivity should be even $\endgroup$ Nov 6 '17 at 21:27
1
$\begingroup$

Vertex connectivity can be even or odd. (The bowtie graph with 5 vertices has even degrees but connectivity 1 which is odd. $K_3$ has even degrees but even connectivity of 2).

Edge Connectivity Must be Even
G has an edge cut [$S,\overline{S}$]
The size of the edge cut |[$S,\overline{S}$]| = κ'(G)
Let m = |E(G[S])| (the number of edges in the subgraph induced by S)
Then we sum all degrees in S
$\sum_{v∈S}d(v) = 2m + κ'(G)$
Since the sum of all degrees is always even and all vertices have even degree, this implies that κ'(G) is also even

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.