2
$\begingroup$

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.

Give some clue please!

Thanks anyway!

  • 0
    What is a point of articulation?2012-09-28
  • 0
    @Graphth A point of articulation is another name for a cut-vertex.2012-09-28
  • 0
    Okay, so we're talking a 2-connected graph such that if we delete any edge, it becomes only 1-connected.2012-09-28
  • 0
    A triangle itself would be considered critical under this definition would it not? That kinda violates the first property.2012-09-28
  • 0
    @EuYu I'm sorry.. I corrected the property: excluding the triangular graph (three points, three edges).2012-09-28
  • 0
    @EuYu Please look at this http://math.stackexchange.com/questions/208742/how-to-prove-the-next-properties-for-critical-graph.2012-10-07

1 Answers 1

1

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. example

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. nested cycle $C$
  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$. cycle with P

  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.

  • 0
    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.2012-09-29
  • 0
    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.2012-09-29
  • 0
    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 C12012-09-30
  • 0
    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.2012-09-30
  • 0
    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.2012-09-30
  • 0
    Wow... If by "connected C1 to C2" you meant that there is some path from some vertex of C1 to some vertex of C2, then I got it. Nice! What do you think about other properties? It is very interesting. Tnak you!2012-09-30
  • 0
    Yes, that's precisely what I meant. Another way to see it is to consider the connected components leftover by removing the triangle from $G$. Each component must be connected to atleast two vertices of the triangle (otherwise removing that vertex will disconnect the component). Such a configuration will again cause problems. As for the remaining problems, I don't think I've made any real progress.2012-09-30
  • 0
    I got the idea! Very nice. And I got this "Since there are no vertices of degree 2, any cycle of G must be part of a nested cycle", but how to say it more fully (expanded).2012-10-01
  • 0
    The way to prove it would be to consider a neighbor of some vertex on the path. There exists another cycle containing that neighbor and the other vertices on our cycle. Use this to show that there must be a nested cycle.2012-10-01
  • 0
    Why do you think that there is another cycle? If we take the neighbors in the cycle C, that exists cycle containing these neighbors - this is also C. I'm sorry for this stupid question, but I want a clear proof.2012-10-03
  • 0
    I'll be a bit more explicit. In a biconnected graph, every pair of vertices is contained in a cycle. If you take a neighbor $u$ of a vertex $v$ in the cycle $C$, then so far, there exists a single (vertex independent) path from $u$ to any vertex of $C$, namely the path through $v$. There must necessarily be another path, since the vertices are pairwise cyclic. The new path and the existing cycle will then form a nested cycle.2012-10-03
  • 0
    By the way. I found this very nice [book](http://books.google.ca/books?id=q2MAF1vYuWQC&pg=PA12&source=gbs_toc_r&cad=4#v=onepage&q&f=false) 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.2012-10-03
  • 0
    You are so amazing. I will read this book with pleasure! It's a pity that not all available for free viewing.2012-10-03
  • 0
    But I don't see the proof for second property (I see just description of Corollary 3.3)..2012-10-03
  • 0
    From the first corollary, a graph is minimally $2$-connected iff it is biconnected and no cycle has a diagonal. A biconnected subgraph of a graph with no diagonals also has no diagonals and hence is also minimally connected.2012-10-03
  • 0
    Thanks for all the explanations, all of them are perfect. About the third property, as I understand it proves a more stronger statement in the book.2012-10-03
  • 0
    Yes, they prove that there is necessarily a vertex of degree two on any path joining two vertices. Of course this shows that there is at least one such vertex (since there must be at least one path).2012-10-03
  • 0
    I'm sorry for this, but can you help me with the Theorem 3.6..2012-10-04
  • 0
    You should probably ask another question. It's too inconvenient to help you through the comments. Plus this answer is starting to get a little too large.2012-10-04
  • 0
    Ok. I'm sorry. I just can't understand the meaning of this term "compatible" vertex. It is the last question for this big question.2012-10-04
  • 0
    They define compatible vertices in the book. It's essentially the "no diagonal" requirement in disguise. If you have a biconnected graph, then take two arbitrary vertices $u,\ v$ and any path $P$ joining them. Suppose the vertices are not compatible so that there is some edge $e$ joining non-adjacent vertices on $P$. Since the graph is biconnected, there is another vertex-independent path joining $u,\ v$. $P$ and this new path form a cycle. But then $e$ will be a diagonal of this cycle. So that in a biconnected graph, $u$ and $v$ will be compatible iff no cycle containing them has a diagonal.2012-10-04
  • 0
    Hmm.. But in the book the author say "Note that two non-adjacent vertices of C^k (k >= 4) are compatible". But you said "u and v will be compatible iff no cycle containing them has a diagonal". This is inconsistent explanations I think.2012-10-04
  • 0
    I assume $C^k$ is the cycle graph? Certainly a cycle graph has no diagonals....2012-10-04
  • 0
    Nice. The night time for me is time of misunderstanding. Gold medal for you! You a nice teacher. Thanks.2012-10-04
  • 0
    Tomorrow I will ask about new properties (and about the third properties of this question) into a new question. Please if you have a little time for this (or just for the third part), join. Thank you.2012-10-06