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

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