retagged by
1,108 views
4 votes
4 votes

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$
retagged by

3 Answers

Best answer
6 votes
6 votes

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.$

selected by
2 votes
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.
0 votes
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.

Related questions

0 votes
0 votes
2 answers
3
Shivam_j asked Oct 16, 2022
669 views
Class B network on the internet has a subnet mask of 255.255.119.0 what is maximum possible hosts per subnet. Assuming Classfull Addressing Scheme
1 votes
1 votes
1 answer
4
Anjali2002 asked Sep 18, 2018
324 views
If A∆B = (A intersection B) whole complement than the universal set is??