Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a new question about Critical graph, because the previous question about it is became too big.

Let me remind. 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$.

Previous question.

How to prove the next properties:

  • $\forall G$, where $G$ is Critical $\Rightarrow$ $\exists v \in V$ and $deg(v) = 2$. For this properties respected @EuYu gave the proof, but I can not fully understand all of it right there (regarding the first item of the proof). Maybe somebody or the author can explain me some moments of this or show another proof.
  • Is it true or not (If it is true that prove otherwise give a counterexample). If $G$ is Critical graph $\Rightarrow \forall w \in V$ , $ deg(w) \ge 3$ , $\exists u \in V$ , $deg(u) = 2$, that edge $(u, w) \in E$.
  • If $G$ is Critical, $|V| \ge 4$ $\Rightarrow$ $|E| \le 2 \times |V| - 4$.

Respected @EuYu also gave the incredible book which outlines some of the above properties (and other) for Critical graph. The book calls Critical graphs as Minimally 2-connected graphs.

In this book there is the proof about first property (more powerful proof "Theorem 3.6. Every $x - y$ path contains a vertex of degree 2"). But I didn't understand it (there are contradictions for me). If someone will understand this, please tell me!

In this book there is the theorem about third property ("Theorem 3.10. A minimally 2-connected graph of order $n$ $\ge$ $4$ has size at most $2 \times n - 4$. Given $n \ge 4$ the complete bipartite graph $K(2, n - 2)$ is the only minimally 2-connected graph of order $n$ and size $2 \times n - 4$."). But why we can't have a Critical graph with a large number of edges with $n$ vertices?

Probably in this book there is something helpfull for second property.

Please help with something. Thanks anyway.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I feel somehow obligated to see this through. I don't have time to provide a detailed explanation of the proof of Theorem 3.6, but I can provide answers for the remaining two questions.

For the second point you mentioned, I'm not sure where $v$ suddenly came from. Assuming you mean $w$ and $v$ to be the same thing, you're basically asking if every vertex of degree $3$ or more is necessarily connected to a vertex of degree $2$. The answer to that is no. Here is a counter-example.

counter-example

Vertices $u$ and $v$ both have degree $3$ and are connected to only vertices of degree $3$.

For the third point, intuitively the more edges we add, the less likely it is for the graph to remain minimal (the word minimal itself suggests that it has to be small). To get an idea of why this should be, note that every edge we add to a graph of $n$ vertices brings it closer and closer to $K_n$ (the complete graph on $n$ vertices) and $K_n$ is about as connected as it gets. So the more edges we add, the more connected we expect the graph to be.

To obtain an actual proof of the bound, I will give a proof of Theorem 3.10

Proof: From Theorem 3.8, we can separate the graph $G$ into it's forest components and it's vertices of degree $2$ (the set $D$). Suppose that there are $k$ vertices in the forest and that the forest has $c$ components. Then there are a total of $k - c$ edges in the forest (recall that a tree has precisely one more vertex than edges, so that a forest of $c$ components has precisely $c$ more vertices than edges). So the total number of edges in $G$ will be given by the edges of the forest and the edges connected to $D$, of which there will be precisely $2(n-k)$ since there are $n-k$ vertices of degree $2$ by assumption. The total number of edges then satisfies $$|E| = 2(n-k) + k - c = 2n - k - c$$ to obtain an upper bound, we must minimize $k$ and $c$. There must be two components and each component must have at least one vertex, so $k,\ c\ge 2$. This consequently gives $$|E| \le 2n - 4$$ Equality is reached when there are precisely two vertices of degree greater than $2$. It follows that each of the vertices in $D$ will be connected to both of these vertices. The resulting graph is precisely the complete bipartite graph $K(2,\ n-2)$. $\square$

share|improve this answer
    
You are sure that the counterexample is correct? I mean this graph is Critical? If I remove edge which connects two red vertex, then the graph is still bi-connected. Please hit me if it is not. Thank you for your time. –  jofisher Oct 8 '12 at 9:01
    
For example, say you remove the edge connecting the two left red vertices. Then remove one of the red vertices on the right will disconnect the top from the bottom. –  EuYu Oct 8 '12 at 18:33
    
I'm confused. Remove the edge this is remove edge without removing of vertices. No? I think yes. And the red vertices on the right won't disconnect the top from the bottom.. –  jofisher Oct 8 '12 at 21:34
1  
Would you like to start a chat? I don't want the comments to get bogged down. –  EuYu Oct 8 '12 at 21:42
1  
let us continue this discussion in chat –  EuYu Oct 8 '12 at 21:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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