Is this an appropriate time to use 'WLOG' in my proof?

Question

A bipartite graph $G=(V,E)$ is known to be connected given its partitions are of equal size $n$, and $|E| \geq n^2 - n + 1$

$G$ is necessarily connected if $|E| \geq n^2 - n + 1$:

1) Based on above $|V|$ = $2n$.

2) WLOG suppose we label the vertices in one partition $\{x_1,...,_n\}$ and those of the other $\{y_1,...,y_n \}$.

...and so on. Is this a normal time to use 'WLOG'?

Not really: it's your choice how you label the vertices. "WLOG" would apply if there was an asymmetry in the conditions that was unimportant in the remaining steps in the proof. — Rob Arthan, Apr 22 '20 at 00:21

score 3 · Accepted Answer · answered Apr 22 '20 at 00:23

The appropriate time to use "WLOG" is when you are moving from a general statement to a more specific statement by making a choice that is irrelevant to the matter at hand.

In this case, you are simply giving names to the vertices. You are not introducing any assumptions, so you don't need to argue that you're not actually losing generality.

If, later in the proof, you wanted to make an argument based on the order of the vertices, you might say:

WLOG, suppose that $x_1 \leq x_2 \leq \cdots \leq x_n$. Then ...

In this case WLOG is appropriate because you are introducing an additional assumption, but it does not affect the generality of your argument as (if you needed to) you could simply relabel the vertices as you desired.

score 2 · Answer 2 · answered Apr 22 '20 at 00:21

No, this is not an appropriate use of "WLOG". "WLOG" is for when you are making an assumption that might be false, but for some reason (e.g., symmetry), if you prove the result under that assumption then the result without the assumption follows easily. Here you are not making any assumption: you are simply giving names to the vertices.

It would be appropriate to use "WLOG" if the proof had started with a statement like

Let $V=\{x_1,\dots,x_n,y_1,\dots,y_n\}$.

Then, since the $x_i$ and $y_i$ have already been defined, it's not necessarily true that the two sets of the partition are $\{x_1,\dots,x_n\}$ and $\{y_1,\dots,y_n\}$, which is why "WLOG" is needed. But in your proof, where you have not yet defined the $x_i$ and $y_i$ at all, there is no assumption needed to label the two sets in this way, since you are just defining new variables.

score 1 · Answer 3 · answered Apr 22 '20 at 00:16

1

There is no need for WLOG here. A simpler sentence is this:

Label the vertices in one partition $\{x_1,...,_n\}$ and those in the other $\{y_1,...,y_n \}$.

answered Apr 22 '20 at 00:16

lhf

216,483

Is this an appropriate time to use 'WLOG' in my proof?

3 Answers3