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)

The Gateway to Computer Science Excellence

+3 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?

- There are at least two edges that have one endpoint in $S$ and one end point in $T$.
- There are at least three edges that have one endpoint in $S$ and one end point in $T$
- There are exactly two edges that have one end point in $S$ and one end point in $T$
- There are exactly one edge that have one end point in $S$ and one end point in $T$

0

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

+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

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.

52,218 questions

59,895 answers

201,086 comments

118,134 users