# How to prove the non-obvious properties for Critical graph?

In this context the Critical graph is: graph $G = (V, E)$ is Critical, if $G$ is biconnected and $\forall e \in E \Rightarrow G-e$ contains a point of articulation.

$G-e$ is equal to if we remove this edge from $G$.

How to prove the next properties:

• If $G$ is Critical $\Rightarrow$ $G$ is Triangle-free graph (excluding the triangular graph (three points, three edges))

• If $G$ is Critical $\Rightarrow$ $\forall H$, where $H$ is a biconnected subgraph of $G$, $H$ is Critical.

• $\forall G$, where $G$ is Critical $\Rightarrow$ $\exists v \in V$ and $deg(v) = 2$.

The second question for this theme.

Thanks anyway!

-
What is a point of articulation? –  Graphth Sep 28 '12 at 21:44
@Graphth A point of articulation is another name for a cut-vertex. –  EuYu Sep 28 '12 at 21:55
Okay, so we're talking a 2-connected graph such that if we delete any edge, it becomes only 1-connected. –  Graphth Sep 28 '12 at 21:55
A triangle itself would be considered critical under this definition would it not? That kinda violates the first property. –  EuYu Sep 28 '12 at 21:57
@EuYu I'm sorry.. I corrected the property: excluding the triangular graph (three points, three edges). –  jofisher Sep 28 '12 at 22:50

Not a full answer. Actually, with the reference included, it pretty much is.

Here is only the first part for the triangle.

Suppose that we have a critical graph $G$ which is not triangle free. Consider any triangle within such a graph. $G$ cannot be the triangle graph itself, so at least one vertex has a component $C_1$ connected to it (with possibly multiple edges). Let's say $v_1$ connects to $C_1$, $v_2$ to $C_2$ and so on.

I claim that each component is connected to either

a) another vertex of the triangle

b) a component connected to another vertex of the triangle

because otherwise the removal of the corresponding vertex will disconnect the component so the graph is not biconnected. But then if $C_1$ is connected to $v_2$ or a component of $v_2$ the removal of $e = (v_1, v_2)$ will not introduce any articulation point. This is a contradiction. To see this a bit more clearly, consult the example in the image below. Either the blue dotted edge must be present or both red dotted edges must be present.

Edit I may have worked something out for the third part. I will include a sketch with details for you to fill in.

Let $G$ be a critical graph. Then $G$ is biconnected and in particular this implies that there exists a cycle between any two vertices (via Dirac). Suppose for the sake of contradiction that there exists a critical graph which has no vertices of degree $2$.

Lemma: If $C$ is a cycle in a critical graph $G$ then there must not be any edges joining non-adjacent vertices of $C$.

Proof: If there exists any such edge, then removing it still leaves the graph biconnected and hence the graph is not critical.

Here is a sketch then

1. Since there are no vertices of degree $2$, any cycle of $G$ must be part of a nested cycle.
2. Consider a nested cycle of two layers (shown above) $C$. I've labelled the exterior vertices from $v_1$ to $v_n$ and the interior from $u_1$ to $u_m$. I've labelled edges as solid lines and paths as dotted lines. In the path nested within the exterior cycle, $u_1$ must have another neighbor since it is of degree greater than $2$. Call such a neighbor $w$.

3. $w$ must not be any vertex on the nested cycle itself otherwise the edge $(u_1, w)$ violates the above lemma. Therefore $w$ is distinct from $C$. There is a cycle containing $w$ and a vertex of the exterior cycle. In particular, there exists at least one path connecting $w$ to the exterior cycle. Let $P$ denote the shortest such path from $w$ to some $v_i$.

4. The existence of $P$ creates another cycle (in red) $$(w, P, v_i, \cdots , v_n , v_1 , \cdots, v_k, u_m, \cdots , u_1, w)$$ but edge $(v_1, u_1$ connects non-adjacent vertices of the above cycle and hence the graph cannot be critical.

The above should be enough to prove that there exists a vertex of degree $2$ provided that I made no errors. I will leave you to check through the argument. Of course feel free to ask for clarification.

Edit I found this very nice book which outlines all of the above properties. The book calls your critical graphs as "minimally $2$-connected graphs". The proof for the triangle property is essentially as I outlined, but with much more clarity. In particular there is also a proof of the subgraph property and the vertex of degree two property in the book (actually they prove something significantly stronger). If you are interested in problems like these, you may want to check out the general theory of extremal graph theory.

-
Nice, but: With component do you mean the set of vertices? and Why is there always a C2? And C1 for example can be connected by an edge to v3, then C1 will not give an articulation point. Picture is misleading a little bit. –  jofisher Sep 29 '12 at 13:10
By component, I mean the rest of the graph connected to the vertex. There doesn't always need to be $C_2$, the image only shows one particular example. You can redraw the image with only $C_1$ or you can even add in $C_3$, you should find that the argument holds in all cases. How you select the components is more or less arbitrary, you just need to choose some subgraph connected to the vertex. –  EuYu Sep 29 '12 at 17:28
Hm... "rest of the graph connected to the vertex" - OK. But for example: C1 this is the next vertices {a, b, c}, C2 is {e, f, g}, C3 is {i, j, k}. All vertices of C1 are connected to v1 and so on.. And exists the path from a to e, path from f to j, and from k to c. This is appropriate for your condition. But C1 isn't connected to C2 or C3, or to v2 or v3. And the removal of C1 –  jofisher Sep 30 '12 at 14:31
And the removal of C1 is not the cause of the appearance the articulation point... If I have misunderstood somewhere, please say so. I really want to find a solution to this problem and others. –  jofisher Sep 30 '12 at 14:38
If I've understood you correctly, then this configuration already causes problems. The vertices $b, g, i$ are only connected to their triangle vertices and that means the graph isn't biconnected to begin with. If you disregard these problem vertices (or you connect them), then removing any edge of the triangle will not create an articulation point. Another way to think about is this. In a critical graph, there cannot be an edge connecting non-adjacent vertices in a cycle, but having a triangle necessarily creates that configuration. –  EuYu Sep 30 '12 at 18:55