Made_Easy

Question

The minimum number of edges the graph G should have for the graph G to a 3-connected  and it given that G has 10 vertices ?

Comments

$\binom{10}{3}$

---

is it 23 ?

what is the answer ?

---

 

answer given here is 15 , and  the solution

---

$\frac{1}{2}k V(G)$

how this formula comes?

---

Mam , I don't know...I have also doubt in this..that's Y I'm posting...I think the given solution is  wrong

---

No, the solution is correct

---

daksirp  explain brother

---

Am getting 7. 3 connected means 3 connected components. Make a line graph with 8 vertices rest two are isolated vertices.

---

Connectivity 'k' requires δ(G) ≥ k.

==> 2|E| = ∑ (degrees of vertices)   {For a simple Graph G}

==>2|E| ≥ k * n

==> |E| ≳ (k * n)/2

 

δ - Min Degree

k- Vertex Connectivity

n - No of Vertices

E - Edges

---

@srestha @magma

Please see this

https://math.stackexchange.com/questions/2456972/minimum-number-of-edges-in-a-graph-with-n-vertices-and-k-connected-component

n−k edges will be enough. for k connected graph,

---

Let n is the no.of vertices

 

k is the components,

Minimum no.of edges = n - k

Maximum no.of edges = $\binom{n-k+1}{2}$

https://gateoverflow.in/237427/graph-theory

--------------------------------------------------------------

if k is the Minimum degree

Min. No.of edges = $⌈\frac{kn}{2}⌉$

 

if k is the Maximum degree

Max. No.of edges = $⌊\frac{kn}{2}⌋$

--------------------------------------------------------------

in the question, they given k is components, but in the answer they consider k is minimum degree

---

thanks smsubham  Shaik Masthan

---

@Shaik

$\binom{n-k+1}{2}$ is ok

but how $\left \lfloor \frac{kn}{2} \right \rfloor$??

k is component here, not degree

right?

---

@srestha mam,

in this question, k is component,

i just additionally give the formula, if k is min.degree or maximum degree

---

yes, that's what I told

for component there is no formula like $(kn/2)$

right?

---

yes mam, for components there is no formula like that

---

so, answer given is not correct

ok?

---

yes mam,i already mention that in my first comment of this question.

---

ok, thank u :)

actually I got -ve vote that is why asking

---

your first comment, formula is absolutely wrong, so may someone gave down vote

---

Actually ans will be 7

as min no. of edges they want

3 components , vertices will be divide like 4,3,3