The Gateway to Computer Science Excellence
+2 votes
123 views

Let $G$ $=$ $(V, E)$ be a simple non-empty connected undirected graph, in which every vertex has degree 4. For any partition $V$ into two non-empty and non-overlapping subsets $S$ and $T$. Which of the following is true?

  1. There are at least two edges that have one endpoint in $S$ and one end point in $T$.
  2. There are at least three edges that have one endpoint in $S$ and one end point in $T$
  3. There are exactly two edges that have one end point in $S$ and one end point in $T$
  4. There are exactly one edge that have one end point in $S$ and one end point in $T$
in Graph Theory by Boss (11.1k points) | 123 views
0

sir by dividing the vertices into 2 sets there are atleast 3 edges from each of them,may i know how 3 are not possible sir? @Deepakk Poonia (Dee)

0
Check the 2nd Point in my answer. At least 3 would be wrong answer.

3 Answers

+5 votes
Best answer

Answer : A

Given Graph $G$ is Connected 4-Regular Graph (Connected and every vertex has degree 4).

We show Three things in order to answer this Question. 

1. We show some Connected 4-Regular Graph $G$ such that  some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has more than two edges that have one endpoint in $S$ and one end point in $T.$ 

2. We show some Connected 4-Regular Graph $G$ such that  some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has exactly two edges that have one endpoint in $S$ and one end point in $T.$ 

3. We show that No such Graph is Possible such that some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has less than two edges that have one endpoint in $S$ and one end point in $T.$ 


1 :

We show some Connected 4-Regular Graph $G$ such that  some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has more than two edges that have one endpoint in $S$ and one end point in $T.$ 

For instance, Take $K_5,$ It is Connected 4-Reg Graph. Now Partition $V$ into $S,T$ such that Exactly one vertex is present in $S$ and other 4 vertices are in  $T.$ Now You have $4$ edges between Partition  $S,T.$


2 :

We show some Connected 4-Regular Graph $G$ such that  some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has exactly two edges that have one endpoint in $S$ and one end point in $T.$ 

Let $K_5^-$ be the same Graph as $K_5$ with One Edge Removed from it. Let's call the End Vertices of the Removed Edge as $a,b.$ 

Now, Take $T$ as $K_5^ -$ and $S$ as $K_5^-$ And Connect the  vertex $a\in T$ with $a\in S $ And connect $b\in T$ with $b \in S.$

Now you have 2 edges present between the Partition $T,S.$


3 :

We show that No such Graph is Possible such that some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has less than two edges that have one endpoint in $S$ and one end point in $T.$ 

Clearly, It is Not possible to have Zero Edge between the Partitions $S,T$ because of Connectedness of the Graph $G.$

Now we show that No such Graph is Possible such that some partition of $V$ ( into two non-empty and non-overlapping subsets $S$ and $T$) has Exactly One edge that have one endpoint in $S$ and one end point in $T.$ 

For proof by Contradiction, Let's assumes that For some such Graph $G$, such Partition $S,T$ exists such that Exactly one edge is going between $T$ and $S$. Now using the Fact that ""Every Graph has Even number of Odd degree vertices", we can show that such Graph $G$ is Not Possible.

 

For the Subgraph $T,$ Only One vertex is of Odd Degree which is Not possible. So, We can say that such Graph $G$ is Not Possible.

Notice that $v_1v_2$ is a Cut edge. So, We can also say that "A Connected 4-Regular Graph can Not have a Cut Edge."

Moreover, You can also say that "A 4-Regular Graph can Not have a Cut Edge." (Same above proof can be used)


Now using Point 1,2,3, We can say that Answer will be Option $A.$

by Boss (26.1k points)
selected by
0
Thanks.
+2 votes
There will be atleast 2 edges with one end point in S and other in T because given degree of every vertex is 4 and hence Euler circuit exist then we need one edge to enter to the set T and we need one more edge to leave from T hence there will be atleast 2 edges.
by (147 points)
0 votes
If G = (V,E) has n ≥ 3 vertices and every vertex has degree ≥ n/2 then G has a Hamilton circuit ....so if Hamilton circuit is there definitely we can visit all vertices and between two partitions once we need to go to the second partition and coming back ......so at least  two edges should there for Hamilton  circuit.
by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,155 answers
193,759 comments
93,733 users