recategorized by
3,636 views

2 Answers

Best answer
2 votes
2 votes
The Handshaking theorem states that,

$\displaystyle{\sum_{v \in V}{deg (v_i)} = 2 \times \mid E\mid}$

Which means, $\text{Each edge contributes twice to the sum of the degrees of all vertices.}$

$\text{Sum of degree of vertices = 2 } \times Edges$

Now, the graph has $35$ Edges.

∴ $2 \times Edges = 2 \times 35 = 70$ is the Maximum Sum of degree of the vertices.

We don't know the number of vertices.

So, we assumed the total number of vertices will be $n$

Condition given is "All vertices are of degree at least $3$"

Sum of the degree of vertices = $3 \times n$ $\qquad \left[ \text{∵ All vertices are of at least degree 3} \right ]$

∴ Minimum sum of degree of vertices will be $3n$ which will be less than or equal to $70$ because $70$ is the Maximum Sum of degree of vertices.

∴ $3\times n \leq  2\times(35)$

   Or, $n  \leq \dfrac{70}{3}$

   Or, $n \leq 23.33$

∴ $\color{Maroon}{\text{Largest possible number of vertices in the graph must be }} \color{Green}{23}$ $\color{teal}{\text{ as we can't take the fractions & will take only the whole number.}}$
edited by
3 votes
3 votes
In any Undirected Graph, We have degree sum formula that :

$\sum_{v \in V} deg(v) = 2\left | E \right |$

Where $\left | E \right |$ is the number of edges.

(We can prove this formula by the fact that every edge in any undirected graph contributes the sum of $2$ in the degree sum formula)

Hence, Just apply this formula :

Let All the vertices have Degree 3(i.e. Let Every vertex have minimum degree possible )

Then, $3 \times n \leq 2 \times 35$

Hence, $n \leq 23.33 $

Hence, Maximum number of vertices = 23
edited by

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
3 votes
3 votes
0 answers
3
Kabir5454 asked Jan 2, 2023
426 views
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
0 votes
0 votes
0 answers
4