0
$\begingroup$

Question

Consider the statement below-:

$\text{1.In simple graph with 6 vertices,if degree of each vertex is 2 ,then graph is connected}$

$\text{2.In simple graph with 6 vertices,if degree of each vertex is 2 ,then graph is Euler}$

$\text{3.In simple graph ,if degree of each vertex is 3 ,then graph is connected}$

My Approach

$1.\text{Using Handshaking lemma,}$

$2+2+2+2+2+2=2 \times |Edges| $

$\text{number of Edges}=6$

Thus a simple graph having $6$ vertices and $6$edges and each having degree $2$ will be connected because it will also be a simple cycle.


$2.$As graph is connected and degree of each vertex is even ,thus it will be a Eulerian graph


$3.$ If degree of each vertex is $3$ , then we cannot say anything about its connectivity. It may be connected or disconnected.

Am i correct? I am not sure about $3$. Please help

$\endgroup$
  • $\begingroup$ Why downvote to my question ? Have i represented question bad?Have i asked a homework question? Am i asking directly for a answer ?Well i have represented it well +shown all my work+asking for a hint.If still someone(who downvoted) thinks it is a bad framed question , then please comment your valuable suggestion so that i will not repeat it again .Downvoting --> you are smart. $\endgroup$ – laura Nov 10 '17 at 7:49
1
$\begingroup$

Answer to all cases are "not necessrily". An example for the first two questions is a disjoint union of two triangles $K_3$, and for the third a disjoint union of two tetrahedra $K_4$.

$\endgroup$
  • $\begingroup$ Yes you are correct .but how to derive your example mathematically ? I mean I have $n$ vertex $n$ edges and degree of each vertex is $2$ All are the properties of simple cycle. $\endgroup$ – laura Nov 10 '17 at 7:39
  • $\begingroup$ @laura These properties are necessary for a cycle, but not sufficient. They are necessary and sufficient conditions for a disjoint union of cycles. $\endgroup$ – Alex Ravsky Nov 10 '17 at 7:43
  • 1
    $\begingroup$ ok thanks a lot $\endgroup$ – laura Nov 10 '17 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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