discrete-math

[agile lava]

How to solve this? I don't even understand what is relaxed k-coloring

[stray reef]

a relaxed k-coloring is a k-coloring where you don't require that all edges connect vertices of different colors

rather, the number of good edges (i.e. edges connecting different colors) is now an objective function to be maximized

[agile lava]

so, what I think is, since there's 4 colors, the probability for a good edge (both ends have different colors) are 1-4C1/4C1*4C1=3/4

I could see the number 3/4 showing here but how to link to the final answer

[stray reef]

assign every edge a score of 1 if it's good and 0 if it's bad

the expected score of each edge is 3/4

therefore the expected number of good edges is 3/4 |E|

and max good edges is obviously ≤ |E|

[agile lava]

I see, thanks a lot

[agile lava]

arithmetric sequence, B

[potent oracle]

Wa...I actually got that right

[potent oracle]

@light path

:c

[light path]

if this is a quiz you probably shouldn't be asking for help

[potent oracle]

Shouldn't be but it's the only hope I have left :c

[light path]

life doesn't end when you fail a test

[potent oracle]

For me it does. It's the only course I don't understand and I need it to get the scholarship

[unreal stump]

[light path]

there are a limited number of scholarships

if you didnt study enough you shouldnt take it from someone who did

[potent oracle]

there are a limited number of scholarships
@light path
I don't blame you for being oblivious as it is I. I'm not taking from someone who did. If you knew the disposition of the college it would be much different in perception

I never cheat so this is a new low...I shouldn't and you're right

[coral raven]

woah, wicked deja vu just now

[light path]

I'm glad you made that decision

[near prawn]

damn, character development

[pale epoch]

redemption arc

[unreal stump]

What about the 2nd betrayal arc?

[errant bear]

top 5 anime comebacks

[potent oracle]

🤣 it was something

[rugged pebble]

can someone help me with transitive closure
for this relation {(a,a), (a,c), (b,a), (c,a), (a,1), (1,2)}
i got this {(b,c), (c,1), (b,1), (a,2), (b,2), (c,2)} but idk if its right

[silk coyote]

Are there some good techniques to get the closed form for a recursive function?

Like tips I should know?

[unreal stump]

Generating functions exist

[silk coyote]

Thanks for the info

[rugged pebble]

@unreal stump do you think you can help me?

[weary tiger]

hi. would a kind sole please write out the way to solve this kind of problem:

like these ones

what is an efficient and easy to understand way of solving this?

i can solve regular modular arithmetic and systems of equations in modular arithmetic, just not sure about his kind of questions

please ping me if answering. thank you

[bronze cosmos]

lol sid i would use a calculator for problems like those

euler’s theorem doesn’t help at all

the best method i know of is to write e in binary and calculate a^(2^k) mod n for each natural number k such that 2^k < e, and then writing e in binary

for example, in question (a),
calculate
4995^1 (mod 9208),
4995^2 (mod 9208),
4995^4 (mod 9208),
4995^8 (mod 9208),
4995^16 (mod 9208), and
4995^32 (mod 9208).

notice that at each step, you can easily calculate using the previous step

for example, after calculating
4995^2 (mod 9208) = 3497,
you then know that
4995^4 (mod 9208) =
(4995^2)^2 (mod 9208)=
3497^2 (mod 9208), which you can then calculate

so at every step, you square the result from the previous step and then reduce mod 9208

finally, 33 = 32 + 1 (this is the “binary expansion” of 32)

therefore
4995^33 (mod 9208)=
(4995^32 * 4955^1) mod 9208
and then multiple those results together from what you got and reduce one last time mod 9208 and that’s it

i’m also now realizing that the number was 4955, not 4995 but whatever you get the idea

does that make sense @weary tiger ?

[vast narwhal]

I was told that this process is actually computationally fast as well

[vale ibex]

is this right?

[weary tiger]

yes that makes sense thank you

[brave lava]

https://i.imgur.com/WyQt941.png

can anyone check my a_n general solution?

I got r1 = 3 and r2 = 2 for my values

then plugged into my a_n general equation

[brave lava]

nvm

i had the variables switched

im good now

[icy parcel]

hey guys

can someone help me understand what should we do in step 3)

like generally

not only in this example

i saw the correction but im not understanding a thing

[minor dagger]

i think its asking for the equivalence classes

[stray reef]

yeah it's the set of all equivalence classes

[icy parcel]

what is that

[stray reef]

wait did you do a and b

[icy parcel]

if someone can join vc it would be easier, but what I understood in these type of problems, if we want to check if the relation is equivalent we need to check if it's reflexive, symmetric and transitive

the b) is kinda easy

but 3 I have no clue at all

[stray reef]

so

in b you found the equivalence classes of 1 and -1

[icy parcel]

lemme just refresh my mind of what was it

1 sec I just woke up

[stray reef]

but you did b

[icy parcel]

ok yes I remember

[stray reef]

you said you did b

you found the EC of 1 and the EC of -1

[icy parcel]

yes

[stray reef]

in part c you need to find all the possible ECs under this relation

which it should be obvious that since $\overline{1} = (0,+\infty)$ and $\overline{-1} = (-\infty, 0)$ there are no other ECs since everything is already in one of those two

[vital dew]

Ann:

[icy parcel]

the eq is every x that's in relation with the number we want to find inside the set right?

[stray reef]

wording...

ok yeah whatever

there is no way to phrase it that is not a mouthful

yes

[icy parcel]

sorry I was french educated

but in university it's american system so Im not familiar with the wording in math

so what are the steps to solve the 3? like I know the result now right?

[stray reef]

yes, the only "step" is to acknowledge that you've found all the equivalence classes already

[icy parcel]

so in 3) generally they ask to find all the EC of R ?

but isn't the $\overline{1} = (0,+\infty)$ and $\overline{-1} = (-\infty, 0)$ only for 1 and -1? or since it has every element in here, so the answer of all of the ec would be inside this interval ?

[vital dew]

Fillory:

[stray reef]

every positive number has (0, +∞) as its EC

every negative number has (-∞, 0) as its EC

there is nothing else in R*

[icy parcel]

I'm looking at the answer now but not familiar with the way it's written, can I send it here?

[stray reef]

sure

the wording of the answer may be fucked up for all i know

[icy parcel]

if you can help me understand it pls

[stray reef]

wow the handwriting

i mean

eh

this is unnecessarily terse imo

[icy parcel]

yh...

[twilit sierra]

guys

what is the cardinality of A={{1},2,3}

[stray reef]

what do you think it is

[twilit sierra]

im lost between 3 or 4

are we supposed to count 1 twice as its inside a set itself

[stray reef]

no

{1} is an element of A, 1 is not

[twilit sierra]

so the cardinality is 3

how about P(A)

[near prawn]

what about it

[twilit sierra]

in that case P(A) is 8?

[stray reef]

P(A) is a set not a number

[twilit sierra]

we have a formula P(A)=2^A

[stray reef]

P(A) is a set not a number

[coral raven]

yes

P(A) is not 8

|P(A)| is 8

[twilit sierra]

the | | mean cardinality?

[near prawn]

yes

[twilit sierra]

when we have to prove or disprove an equation like that one

and we find that the ven diagram is diferent

is there a certain method to find which set would be an empty set and which would have an element

like here we said A={1} B={1} C=empty set

[minor dagger]

i think you might be schizophrenic

[shy drum]

New Document(2)

sorry to be asking such a simple question but I want to be sure

the bottom line has {x , {z}}

what is {x,{z}} in this context?

[stray reef]

uh

{x, {z}} is the set whose only elements are x and {z}

[shy drum]

is {z} considered to be a set of it's own?

[stray reef]

it's not "considered to be" a set, it is a set

[shy drum]

Ok, thanks ^^
So both statements are true

[stray reef]

no

[shy drum]

oh?

[stray reef]

second one is false

[shy drum]

but I thought that z is a subset of this set?

why is second one false?

[last timber]

because subset is {{z}}

though {z} is indeed set, in the context of {x,{z}} we have {z} as element

if it helps you can denote {z} by y and you have {x,y} and {y} as its subset

[shy drum]

so...

[stray reef]

z may not even be a set

[shy drum]

it would be true if it was {x,z} but not {x,{z}} correct?

[stray reef]

no.

[last timber]

still would be wrong, because z is element

[stray reef]

z may not even be a set

[last timber]

subset of A is a set including elements of A

[shy drum]

in what case that statement would be true?

[last timber]

which statement?

[shy drum]

How would it need to be rewritten to be correct?

[vital dew]

Commander Vimes:

[shy drum]

oooh

so if it was {z} sideways U {x,z} then it would be correct?

Honestly I feel like I'm wasting your time, could someone recommend a resource regarding this exact question?

I would read up a bit more before asking this

[last timber]

so if it was {z} sideways U {x,z} then it would be correct?

i mean any book on set theory even basics treats this q

[shy drum]

I think I'm starting to understand

In this case A is false and B is true

correct?

no

[last timber]

does {u, {y}, t} contain element y?

[shy drum]

crap

I read it incorrectly

maybe I should move to #help-1 ?

[last timber]

nah

[viral patio]

From

#❓how-to-get-help

Rule 3

Stick to one channel and don't post the same question in multiple channels. Please don't ask for help in other channels if no one is responding in the one you have posted your question in.

[shy drum]

ok as long as I'm not bothering anyone

I will have a lot of silly questions

Both are false

[sand turret]

hello

I was experimenting with graph coloring, thinking about different sequences to traverse the graph in in order to produce an optimal coloring

I thought of decreasing degree sequence

but then I thought BFS would be better

but I found an SO answer where it's stated BFS would not produce an optimal sequence

so why is decreasing degree sequence better than BFS?

[last timber]

wym by optimal coloring

[sand turret]

minimum no. of colours required

satisfying the usual no two neighbouring nodes have same color condition

[last timber]

well, then first of all, see that bfs does not put any conditions on root

[stray reef]

so you want an algorithm to find the chromatic number of your graph?

[sand turret]

well, then first of all, see that bfs does not put any conditions on root
@last timber I have taken one of the highest degree nodes as the source of BFS

so you want an algorithm to find the chromatic number of your graph?
@stray reef I want an optimal coloring

i.e. with min no. of colors

so I need the chromatic number as well as the coloring itself

[last timber]

well, i guess the reason why decreasing degree is preferable

is that contrary to bfs, on each step dec degree would take a key places of your graph

[sand turret]

can I use BFS from highest degree node and dec degree in each layer?

[last timber]

i mean i do not have paint on my distro now but imagine a graph where you have for example vertex a on one end of the graph would have deg 10 then there is a bunch of vertices of deg 1-2 and then on other end there would be vertex of deg 9

how would bfs proceed here?

[sand turret]

normally but each layer will be sorted acc to degree

so dec degree seq is the best I can do?

[last timber]

idk if this is the best but it seems preferable here

[sand turret]

Okay, I vaguely understand the reasoning behind that

I mean it's easy to see that algo working in a graph and feel that it's better

can you formally prove one algo is more optimal than the other on average?

[last timber]

well, for example you can prove that one is linear and second is say O(n^2) and then the former is preferable

or you can show that for one preconditions are weaker and one algo is in general more capable

[sand turret]

yeah that's understandable but any seq I use will give O(V+E) complexity ig

[last timber]

well if you have O(V+E) then you can analyze memory complexity etc

[sand turret]

but I want to compare the optimality of the algo not the performance

i.e. whether one gives less no. of colors on average

[last timber]

well wait

if they give diff no. of colors

then one of them would be wrong

[sand turret]

nope

[last timber]

because one graph cannot have two optimal colorings in the sense of no. of colors

[sand turret]

Neither will give optimal coloring in every possible case

it has to be closer to optimal or optimal coloring in more cases

[last timber]

well, then it will require probabilistic analysis ig

[sand turret]

hmmn yeah ig

[rustic dew]

Can someone help me with a problem? I know I have to use rules of inference with quantifiers to prove an argument, but I'm lost as where to start.

[mystic moss]

@glacial elm wdym

[marsh hatch]

I'm taking a graph theory course and I'm working through one of the problem books. One question says
What is the largest number of cuts that can be made in a volleyball net (5×10) so that it does not fall apart?
For context, this comes right under the topic "Eulerian and Hamiltonian Graphs". I've looked through all the theorems and definitions but I can't figure out what criteria to use to determine 'when it will fall apart'.
I take it that a cut = edge deletion. And 'fall apart' = no longer connected. So the question is asking how many edges can be deleted in the 5 x 10 net such that the resulting graph is still connected. Is this right?

It seems I simply need to use |E| - |V| + 1

[stray reef]

yeah just leave a spanning tree in

and you can cut everything else

[marsh hatch]

Thanks, that's what I did.

[chilly hull]

Could someone help me with question 3, part h? I think the answer is [2^(n-1)]= {2^(n-1)....2^(n)-1] but I’m not sure..

[chilly hull]

<@&286206848099549185>

[rugged pebble]

can someone help me with transitive closure
for this relation {(a,a), (a,c), (b,a), (c,a), (a,1), (1,2)}
i got this {(b,c), (c,1), (b,1), (a,2), (b,2), (c,2)} but idk if its right

[opaque fern]

Is this channel occupied?

[tame hound]

hi, anyone here?

[weary tiger]

I need help understanding something in modular arithmetic

first, is this correct?

please ping me if answering. this involves a bit of a discussion

[errant bear]

yes its correct

[knotty mauve]

I'm still new to discrete math, can someone help me with this questions?

[knotty mauve]

<@&286206848099549185>

[analog sonnet]

What have you tried

[knotty mauve]

Question 16

None

I just need your help with just one of them

[analog sonnet]

Do you know what the statement $A\cap B\subset A$ means?

[vital dew]

Rijinaru:

[knotty mauve]

Yes

[analog sonnet]

Can you explain it in your own words?

[analog sonnet]

,rccw

[knotty mauve]

Is this how it is done?

[analog sonnet]

Yeah, that seems like a good proof

I thought you just said you haven't done anything

But you seem to be doing quite well for yourself already

Keep it up!

[knotty mauve]

I'm not confident with my answer

That's why I ask

[analog sonnet]

Please do show your work in the future though, even if it's scratch work

[slim idol]

Maybe add : Choose a random x

[analog sonnet]

It saves time for all of us

[knotty mauve]

Okok

Thank you

[analog sonnet]

imo the "if x in A intersect B" already implies that you're looking at a generic element x

But yes, add it if you want to be very rigorous

[knotty mauve]

Thank you

[distant bobcat]

Is the power set of natural numbers under the operation union a set? Im guessing no, since although it is closed I dont think that it has an identity element.

[unreal stump]

You mean group?

Or monoid

There's an identity (null set),but there's no inverse

[distant bobcat]

yes, a group sorry

oh yes, also meant the inverse. Terrible wording (

[near prawn]

try it again

[distant bobcat]

What would I need to prove for a set to be a monoid? Im only familiar with groups, fields and rings so far in my course.

[sour arrow]

A monoid is a group without inverses @distant bobcat

So, prove it is a group, then erase the inverse part.

[last timber]

maybe not erasing but just not proving that inverse exists

[distant bobcat]

What would you prove for a subgroup of a monoid then? The identity and that its not empty?

[last timber]

subgroup of monoid?

[sour arrow]

Only cool kids erase the inverse part

I guess you could call it a submonoid, haha

Closed + has identity

[unreal stump]

A monoid could have a subgroup

[distant bobcat]

Thanks)

A monoid could commute as well right? Does it have a special name like the abelian group?

[unreal stump]

abelian monoid?

[distant bobcat]

who knows except google)

[tidal plinth]

Commutative monoid

[untold cliff]

can you find a graph from the third power of its adjacency matrix?

[olive sun]

Translation: Using mathematical induction, prove that:

Can anyone help me with this?

[coral raven]

nice av

what have you tried

[coarse sparrow]

Hey boys , would appriciate if you tell me if i got it right

[stray reef]

what is Phi?

also uh

channel occupied

[coarse sparrow]

First Incorrect , 2nd and 3rd correct and 4th incorrect

[coral raven]

it matters not surely

just set theory

[coarse sparrow]

they are asking true / false

[stray reef]

what is Phi?

[coral raven]

why does it matter

[coarse sparrow]

Empty group

[stray reef]

empty set*

[coarse sparrow]

set*

yes

[stray reef]

ok now i can express disgust

but yes, #2 and #3 are true while #1 and #4 are false

[coarse sparrow]

Nice , may i ask another question?

need to create

[stray reef]

write out P(C)

then take the powerset of that

[coarse sparrow]

if anyone wants to help with

i would appriciate it*

❤️

need to prove

[weary tiger]

its pretty obvious right

(B\C) isn't in (A\B) so you aren't subtracting any element from (A\B)

(because B\C is a subset of B)

[karmic nymph]

could someone explain why this has 3 internal verticies

i count only 2

[vast narwhal]

I'm guessing internal means more than one edge...

[karmic nymph]

yeah

so can the root be an internal vertex too?

im gonna guess yes

[vast narwhal]

I would say yes... With a tree, any vertex could be a root

[vague fog]

what

how u get 5/16?

[karmic nymph]

read of the ruler

[vast narwhal]

So you wouldn't want to toss out a vertex that would otherwise be internal, but becomes excluded by certain artificial choices. That would be a lot to keep track of if you should change your mind which vertex is the root

[karmic nymph]

So you wouldn't want to toss out a vertex that would otherwise be internal, but becomes excluded by certain artificial choices. That would be a lot to keep track of if you should change your mind which vertex is the root
@vast narwhal ah i see

[vague fog]

bruh what

is this right?

[karmic nymph]

9/16 it looks like

[vast narwhal]

The 8/16 mark is halfway between 75 and 76 on the first one, that's a good thing to keep in mind

I love playing the "bruh what" game when I go to the hardware store. I can pretty much point to any measuring device...

[vague fog]

this? this is 8/16? how tho? are the big lines 5 each?

[mystic moss]

okay, but what if the root has only one neighbor--then is it still an "internal" vertex

[karmic nymph]

i thought internal vertex meant, a vertex with more than 1 edge

[mystic moss]

according to some random pdf from illinois:

so since the root has children, it would be considered an internal node. it's mostly an arbitrary distinction, depends on what you want to do with it

So you wouldn't want to toss out a vertex that would otherwise be internal, but becomes excluded by certain artificial choices. That would be a lot to keep track of if you should change your mind which vertex is the root
@vast narwhal about this--i think if you defined "internal" to be something irrespective of the root, you might as well just define it on an unrooted tree (this is the notion of a leaf, right). so a rooted-tree-specific quality should probably depend on the actual choice of root

[karmic nymph]

slightly confused

the circled nodes are the "internal" ones?

@mystic moss

[mystic moss]

according to the pdf from illinois, yes.

[karmic nymph]

nice, giving the name "internal" is kinda misleading

[vast narwhal]

If you "bent" the top-right edge to where it's facing northeast, it's more apparent as to why...

[mystic moss]

i think you can just think of it as like a waterfall or something, or a river delta.

(interestingly enough, if we "bent" the top-right edge and rooted the tree at the topmost vertex, it would also become "internal".)

[vast narwhal]

It would be a different situation if the edges were pointed, but with unlabeled edges it's sorta arbitrary

[mystic moss]

by rooting the tree we kind of direct the edges, though

hm. every "connected" dag is a rooted tree, right?

no, i lie.

[vast narwhal]

no loops allowed

[mystic moss]

yup

what about this--every dag that stays a dag irrespective of the direction of its edges is a rooted tree? 🤔

[vast narwhal]

I think it's just a wordy way of talking about valence, this internal vs end

[mystic moss]

valence?

[vast narwhal]

how many edges are touching said vertex

[mystic moss]

okay, gotchu. also, "end"?

[vast narwhal]

not internal, only one edge touching

[mystic moss]

okay, so leaves.

[vast narwhal]

woops my bad, yes

"end" is something different - I think it's more like a "leaf at infinity" sort of notion

[mystic moss]

at infinity? so like, on an infinitely large tree?

[vast narwhal]

You could have a tree in the poincare disc model of hyperbolic space, and think of it as reaching out towards the boundary circle at infinity

[mystic moss]

poincare disc model of hyperbolic space?

[vast narwhal]

Here's some cool imagery of it:
https://youtu.be/xHvAqDuWG2M

If you think of a euclidean sphere as being positively curved, with fattened triangles. This is negatively curved, with thinner triangles

[mystic moss]

hm. can we embed this in 3d space like we can the sphere?

[vast narwhal]

The answer is no by Hilbert's Theorem, it was a big question at the time

I think it can be embedded in R^4 though

[neat holly]

😳

[vast narwhal]

Super discrete, lol

[neat holly]

I can see that lmao

I can't wait to try to understand a quarter of what was just discussed

Also, if I may ask, how would I go about doing this?

I've defined a nested interval as $I_1 \supset I_2 \supset ... \supset I_n \supset ...$

wait let me figure out the latex formatting

o

[vital dew]

Rai Bread:

[neat holly]

uh

[vital dew]

Rai Bread:

[vast narwhal]

You want to show that $\cap_i I_i$ contains at least one point

[vital dew]

Apopheniac:

[neat holly]

My professor's hint says something like constructing a Cauchy sequence ${x_n}$ that approaches some number x, and then show x is in every interval $I_n$ and if it's in every interval, then the intersection is non-empty.

[vital dew]

Rai Bread:

[vast narwhal]

That sounds about right. You would want ${x_n}$ to satisfy $a_n\leq x_n \leq b_n$ for each n, this is what it means to have $x_n\in I_n$

[vital dew]

Apopheniac:

[neat holly]

Can we say there's a non-empty set ${a_n : }$ bounded above such that ${x_n}$ is the supremum?

whoops

[vital dew]

Rai Bread:

[vast narwhal]

Yes all of the $a_n$ are bounded by what then? In order to say it's bounded, it can help to state a bound so that the assertion is clear

[vital dew]

Apopheniac:

[grim swan]

each individual a_n is bounded by x_n, but the set of a_n is not necessarily bounded by any x_n

[vast narwhal]

And then you would also want to argue that the supremum that you obtain satisfies what you want: show that it is contained in the intersection of these intervals

[neat holly]

I think it's all starting to come together!

[grim swan]

do you already know every cauchy sequence has a limit?

[neat holly]

Yes

[grim swan]

cause if you know that, you can just say that in this case. if not you can use the supremum idea to prove there's a limit

[neat holly]

It'd deal with the idea of how every convergent subsequence is Cauchy, right?

[grim swan]

i don't think so? any convergent sequence is automatically cauchy

in any case i think we're getting away from what the idea here was

you choose $x_n \in [a_n,b_n]$, then show the sequence of $x_n$ is cauchy, then let $x_n \to x$

[vital dew]

doubledual:

[grim swan]

that's where we were at right?

[neat holly]

I was thinking of saying ${a_n} \lneq {x_n}$ for all $n \in N$ but also that ${x_n} \lneq {b_n}$ for all n

And yes.

whoops

[vital dew]

Rai Bread:

[grim swan]

i think you just want \leq

but ok that is true by how you defined the x_n, what do you do from there?

[neat holly]

I'm not too good at LaTeX. My bad.

Would we start proving for different cases, say, ${a_k}$?

[grim swan]

i'm not sure what you mean by that

[vital dew]

Rai Bread:

[neat holly]

$k \in N$

[vital dew]

Rai Bread:

[grim swan]

so you want to show $x \in \bigcap_{n=1}^\infty I_n$ right

[vital dew]

doubledual:

[neat holly]

asterisk is just correction. I mean to say that if we have such a set $[a_k]$, we can prove for cases when $n \leq k$ and $k < n$

[vital dew]

Rai Bread:

[neat holly]

Yesyesyes

[grim swan]

so you need to show $x \in I_n$ for every $n$

[vital dew]

doubledual:

[grim swan]

so I don't see how the cases come in at all

[neat holly]

Maybe I'm just overthinking the Cauchy Convergence Criterion

I think I see what you mean

[grim swan]

oh are you on the step of proving that the sequence of x_n are cauchy?

or the step where you prove x is in the intersection

[neat holly]

I started by defining a nested interval and then assumed $I_n \supset I_n+1$, so $x_n \geq x_n+1$

Apologies if I butcher the latex

[vital dew]

Rai Bread:

[neat holly]

The +1 is meant to also be subscripted but I have no idea how to do that

[vast narwhal]

$x_n \geq x_{n+1}$

[vital dew]

Apopheniac:

[neat holly]

OH

Thank you!

[vast narwhal]

there's supposed to be an underscore inbetween the x and the brackets, discord chopped it off

[neat holly]

I see the text italicized but I guess TeXit took the raw input anyway

[vast narwhal]

yeah it hates me

[neat holly]

At least I know how to subscript things now

[grim swan]

you can wrap the text in ` if you don't want it to format

discord won't format this

[vast narwhal]

snap cool

[neat holly]

I know that if you put a backslash before a formatting character, it'll prevent Discord from formatting it, too

[vast narwhal]

Like ${$?

[vital dew]

Apopheniac:

[neat holly]

*more like this*

I put a backslash () before it

[vast narwhal]

ah gotcha

[neat holly]

wow it doesn't even show

/ but flipped

[grim swan]

\

just do it twice lol

[neat holly]

Oh yeah I didn't think of that

[vast narwhal]

gonna have to start coming up with street lingo to keep from getting messed with by discord bot grammar nazi

[neat holly]

lmao thank you

Discord hates backslashes

[grim swan]

oh btw going back to the problem, no need to assume the sequence is decreasing

you can do that wlog if that gives you an easier solution though

[vast narwhal]

Discord hates cans too

not wlog, it's just true

[neat holly]

Perhaps I'm just new to Cauchy Convergence Criterion and assumed there'd be a lot to it. I was so ready to introduce an $x_m$ too

[vital dew]

Rai Bread:

[neat holly]

I love cans

[grim swan]

the cauchy sequence of x_n doesn't have to decrease

[vast narwhal]

because the intervals are nested, the endpoints form a monotonic sequence on either side

[grim swan]

yeah the endpoints are monotonic, but the x_n don't need to be

[vast narwhal]

Correct, I was thinking of the $a_n,b_n$

[neat holly]

So we go by assuming that if a sequence is Cauchy, then it is also bounded and the opposite may also be true, no?

[vital dew]

Apopheniac:

[vast narwhal]

Well, everything is Cauchy here, right? The $a_n$ and $b_n$ are convergent and therefore Cauchy

[vital dew]

Apopheniac:

[neat holly]

Oh. yeah! I'm dumb lmao

[last timber]

are u guys trying to prove nested segments lemma?

[grim swan]

yeah we're trying to help rai with it

[neat holly]

Hihihihihi

[last timber]

use axiom of completeness (and hence least upper bound property equivalent to it)

no need in cauchy

[grim swan]

what is the axiom of completeness to you

because to me it's "every cauchy sequence has a limit"

[last timber]

well they are equivalent

[grim swan]

or maybe "sets bounded above have sups"

[vast narwhal]

Heine-Borel, yes there are many equivalent thingies

[last timber]

but i mean have you met the one that if A and B are nonempy and for all a in A and b in B a \leq b then there is c separating them

this one is much more easier to use for the proof ig

[vast narwhal]

We can pick one, and it doesn't require rewording everything

[neat holly]

But would it also count as using the Cauchy Convergence Criterion for proving the NIP?

Though they are equivalent

[last timber]

anyway, the point is that you can prove that for all n a_n <= b_n which is obvious

and a_n <= a_(n+1)

and also a_m <= b_n for all n,m

[vast narwhal]

$a_n$ is increasing here, not decreasing

[last timber]

ye sorry

[vital dew]

Apopheniac:

[last timber]

anyway

crucial is

[vital dew]

Commander Vimes:

Commander Vimes:

[vast narwhal]

wtf aoc is not needed here

[last timber]

and if segments are of arbitrary length you can show that this point is unique

wtf aoc is not needed here
@vast narwhal how would you prove nested segments lemma w/o AoC?

[neat holly]

I'm trying to think of a way to apply like n > m or something

[vast narwhal]

oh lol I thought you meant axiom of choice my bad

i forgot you said completeness earlier instead

[last timber]

well i think we still use choice but implicitly here tho

I'm trying to think of a way to apply like n > m or something
@neat holly well

no actuall need

you can show

https://media.discordapp.net/attachments/496785905474994186/778114806124118016/694042020100046990.png?width=960&height=185

this

by contradiction e.g

suppose there is such pair m, n so that a_n > b_m

[neat holly]

What about $b_m - a_m$?

[vital dew]

Rai Bread:

Commander Vimes:

[neat holly]

Hmmm.

[vast narwhal]

All of the endpoints on the right are to the right of all of the endpoints on the left

[neat holly]

My braaaaain

[vast narwhal]

This is by definition of nested

[vital dew]

Commander Vimes:

[grim swan]

oh i see what you're getting at here, that is definitely one way of doing it

you can do it with midpoints too if you want, and that's what rai's professor hinted to do

[last timber]

no need in midpoints tho

[vast narwhal]

You could even do it with a constant sequence

[grim swan]

yeah i believe you that this argument does not use midpoints at all

it clearly works

[last timber]

https://media.discordapp.net/attachments/496785905474994186/778115144441266236/694042020100046990.png?width=960&height=116

[grim swan]

that isn't what AoC means

[vast narwhal]

If a set is bounded above by b, its supremum is at most b...

[neat holly]

Would this be related?

[grim swan]

but yeah you can just say sup a_n = inf b_n, and that point is in every interval

and that uses the contradiction argument from above

[last timber]

my argument uses the defn of AoC as if A,B are sets such that forall a, b in A,B respectively a <= b holds then exists point c so that a <= c <= b for all a,b

[vast narwhal]

the point would be in every interval without contradiction

[last timber]

https://media.discordapp.net/attachments/496785905474994186/778117166952087562/image0.jpg?width=332&height=443 well yes ray this is visualisation

[neat holly]

I see where the contradiction lies

[grim swan]

@last timber i don't think that statement is equivalent to axiom of choice, i'm pretty sure i can prove it without axiom of choice

[last timber]

by AoC here i meant completeness

[grim swan]

AoC and completeness are super different lol

[last timber]

sorry if i led you to confusion

[grim swan]

yeahhhhh

ok then i'm happy

you were using completeness

[vast narwhal]

So complete and cauchy, these are both notions of completeness.

[last timber]

well one can show that they are equivalent

e.g it maybe easier to show that cauchy is equiv to least upper bound property on R and then it follows

[grim swan]

oh let me just show you guys the midpoint argument since it's actually easy

[vast narwhal]

ok good

[neat holly]

Maybe another thing that gets me is the amount of rigor for proofs that I'm still trying to get a hang of

[grim swan]

so we want to show $x \in I_n$ for every $n$

[vital dew]

doubledual:

[last timber]

btw you can use heavy machinery and use monotone sequence

well not really heavy but overuse

[grim swan]

the sequence $(x_k)_{k \geq n}$ is a sequence in $I_n$ that converges to $x$, using here that the intervals descend

[vital dew]

doubledual:

[grim swan]

so since $I_n$ is closed, $x \in I_n$

[vital dew]

doubledual:

[neat holly]

I thought about it, but perhaps I take "Use Cauchy Convergence Criterion" too seriously

[grim swan]

and thus x is in the intersection

nice and clean

[vast narwhal]

What is x_n defined as?

[grim swan]

just take the midpoint of I_n

to avoid axiom of choice lol

you do need to check that's cauchy, and that is because the intervals descend and the length of the intervals go to 0

[vast narwhal]

ah ok. yes - closed means contains limit points, very quick and clean

[last timber]

in fact btw intervals can be even not closed

crucial is that they are nested

[vast narwhal]

if they're not closed, then you don't get NIP

[neat holly]

All convergent sequences are bounded

[vast narwhal]

take (0,1/n)

[neat holly]

Or something like that

I think

[last timber]

oh ye sorry

[grim swan]

@neat holly i feel like this conversation was really long and disjointed, so i want to give you an outline of the proof. i'll explain the proof which involves cauchy sequences since that was your professor's hint

[neat holly]

I was also going to scroll up and connect the dots either way, but I did learn a lot more than I expected and I thank all three of you for taking your time with me

[grim swan]

we choose $x_n \in I_n$, you can choose the midpoint if you want something explicit

[vital dew]

doubledual:

[grim swan]

you need to show $(x_n)_{n\geq 1}$ is a cauchy sequence

[vital dew]

doubledual:

[grim swan]

when you do that, by completeness, you know there is some $x$ such that $x_n \to x$

[vital dew]

doubledual:

[grim swan]

now you want to show $x \in \bigcap_{n \geq 1} I_n$

[vital dew]

doubledual:

[grim swan]

this means you need to show $x \in I_n$ for every $n$

[vital dew]

doubledual:

[grim swan]

now here's the easy trick to do this:

the sequence $(x_k)_{k \geq n}$ is sequence contained in the set $I_n$, using here that the intervals descend

that sequence obviously converges to $x$

[vital dew]

doubledual:

[grim swan]

and since $I_n$ is a closed set, we conclude $x \in I_n$

and thus $x$ is in the intersection as needed

[vital dew]

doubledual:

[neat holly]

ohmy

[vital dew]

doubledual:

[neat holly]

My mind has been blown

[grim swan]

the big step I left out here was showing that the sequence (x_n) is a cauchy sequence, i'll leave that part to you 🙂

[vital dew]

doubledual:

[neat holly]

I've proven x_n is Cauchy on a previous problem

I can definitely do that one

[grim swan]

great 😄

[neat holly]

I'll keep trying to connect previous dots from the clash of you three great minds

[vast narwhal]

You could argue by Cauchy-ness of another sequence, sometimes that can allow you to avoid having to write as much

[neat holly]

Every convergent sequence is bounded. If I can prove convergence, it'd also be Cauchy?

Also, there's a lemma that states that a Cauchy sequence of real numbers is bounded

[grim swan]

it's easier to prove it's cauchy, then use completeness to show it converges

the basic idea is: the end terms of the sequence are contained inside intervals shrinking to length zero

or use apop's suggestion if you can figure that out

[neat holly]

I'll play around with the ideas for a bit then construct a good proof

Again, I appreciate all of you for taking your time to help me. It all pushes me to continue pursuing mathematics!

[last timber]

you are welcome

[neat holly]

:)

[last timber]

it feels so good when you are useful

[neat holly]

I want to be useful someday

[last timber]

[neat holly]

[lofty mango]

how am i supposed to Prove that if a and b are positive integers such that a|b and b|a, then a = b?

i think | is supposed to be divide

they're positive integers

i don't know what else to say TBH

that's it

i'm supposed to use either direct, contrapositive, contradiction, proof by cases, or mathematical induction

alright

[gritty crescent]

Need help.

I don't understand how assuming the contrary helps here, since the distribution of points is at random. I thought about successively considering triangles of the largest area, and then somehow showing that the distance between the vertices of these triangles will become smaller and that would somehow give a triangle of area<68 but that is too contrived to work it seems.

I'm just stuck now. This is supposed to be solved using pigeonhole principle.

I also considered covering the bigger triangle with smaller triangles, but overlaps might kick in(?)

[last timber]

what it means "triangle of at most 68"

and are points discrete or continuous

[gritty crescent]

Discrete, I suppose, it is irrelevant either ways, no?

The choice of points is random

[pale epoch]

what are continuous points 🤔

[last timber]

i mean

triangle

what are continuous points 🤔
@pale epoch points in string theory

[pale epoch]

but i too wonder what "span a triangle of at most 68 means"

so i take 3 points that not all lie on a line, they span a triangle and ?

[gritty crescent]

The area shouldn't exceed 68

[pale epoch]

ah

[gritty crescent]

The claim says that of the 169 points inside the triangle of side length 100, there must exist a triangle of area less than 68 units

[pale epoch]

give me a second to think

but this is probably just pigeonhole

[gritty crescent]

Yes, it is supposed to be pigeonhole.

[pale epoch]

yeah

you need the added condition though that no 3 points lie on a straight line

otherwise just have all points lie on a line

then there are no 3 points that even span a triangle

anyways...

my first hint is this bad drawing:

[gritty crescent]

Hmmmm

then there are no 3 points that even span a triangle
They span triangles of 0 area, no?

[pale epoch]

if you want to consider a line segment a triangle

then that works too

[gritty crescent]

And is the idea behind that drawing partitioning a triangle using those points?

[pale epoch]

just partition the triangle

[gritty crescent]

Hmmmm

[pale epoch]

whats area of a smaller triangle?

[gritty crescent]

Wouldn't some of the triangles be formed using the vertices of the bigger triangle?

Or is that a non-issue

?

[pale epoch]

what do you mean

right now im not even thinking about the random points inside the triangle

[gritty crescent]

Uh

Look at any of the smaller triangles above except the central one

It is formed using a vertex of the bigger triangle

And I think I shouldn't be including them

[pale epoch]

including them in what?

[gritty crescent]

I was confused nvm

I get your point

I actually considered that before but subsided due to this confusion of mine

But partitioning seems to work

And possibly the only way pigeonhole works

[stray reef]

what does "a triangle of at most 68" mean

does it mean a triangle containing at most 68 of our points inside?

p sure you can argue there will always exist a triangle containing ZERO of our points in its interior

[gritty crescent]

does it mean a triangle containing at most 68 of our points inside?
@stray reef A triangle of area at most 68 square units

[stray reef]

oh

[karmic nymph]

why is "t" an internal vertex ?

[pale epoch]

what's the definition of internal vertex?

[karmic nymph]

a node that has more than 1 children

[pale epoch]

what's the definition of child then

[karmic nymph]

a node that branches of another

[pale epoch]

that's not really precise

[karmic nymph]

b c d are children of a for example

um

is my definition for internal vertex incorrect?

[pale epoch]

correct?

well

t is only a parent node of u

so t has only 1 child, which is u

so if your definition of internal is at least 2 children, t is not internal

all this is assuming that the tree is rooted at a

[karmic nymph]

my definition may be incorrect

[pale epoch]

wikipedia says "An internal vertex is a vertex that is not a leaf"

[karmic nymph]

the answer for b, they include the node t

[pale epoch]

and t is not a leaf

[karmic nymph]

oh

that makes sense ig, i was told its only if it has more than 1 child node :/

[obtuse lance]

it has more than one child node

q and u are both children of t

you're imagining a directed graph that isn't really there because of how it's drawn, you've fooled yourself

@karmic nymph

[karmic nymph]

interesting

its rooted at a tho?

[pale epoch]

ehm, this is a rooted tree at a

at least i assumed that

[karmic nymph]

i mean it doesnt say rooted at a but i assumed it too

[pale epoch]

then v is a child of w if w is the parent of v

[karmic nymph]

The question says "Consider the following rooted tree"

[pale epoch]

and the parent is the unique node that is on a node-root path right after the starting point

so t is the unique parent of u, hence u is a child of t

q is not a child of t, since q is the parent of t

[karmic nymph]

ye

ye, thats if its rooted at a

if its rooted at t, then children are q and u

i think thats what he meant

[pale epoch]

oh yeah

[weary tiger]

"how many letters must be printed so the expected number of occurrences of the string “BANKRUPT” is exactly 1?" Where each character is chosen uniformly at random from the 26 capital letters

how do i approach this

[terse kayak]

,iam adv

[vital dew]

Your roles have been updated!

[coarse sparrow]

Can someone check if i applied the rules correctly?

[quaint star]

Why do you use arrows?

$2+3 \to 5$

[vital dew]

Lunasong:

[coarse sparrow]

ask our dumb teacher

just check it please lol

[quaint star]

Are A, B and C subsets of some universal set? Otherwise what does B complement mean?

And the first statement of the last line is wrong

$(A \cap \overline{B}) \cup ((A \cap \overline{B}) \cap C) = A \cap \overline{B}$

[vital dew]

Lunasong:

[coarse sparrow]

yeah so i should just erase the last line and go straight for what you wrote?

without explaining the reason i can do that?

[quaint star]

I mean, you didn't write any explanations so far

I'm just telling you it's incorrect

I have no idea what you are expected to write

You also didn't answer my question

Are A, B and C subsets of some universal set? Otherwise what does B complement mean?
@quaint star

You can't talk about complements unless it is in relation to some specific set.

[coarse sparrow]

ok here's another version of my classmate

does that look like a right way of showing it?

[quaint star]

No this is horrible

What is the intersection of two statements?

And horrible misuse of the equals sign

[coarse sparrow]

im happy im not the only one whos wrong then

oof

[quaint star]

I like the vague idea behind that better though

Take an element of the left hand side, and show it belongs to the right hand side

And the reverse

[coarse sparrow]

yeah they asked to show only 1 way

sorry i forgot to mention

my bad

is that right if so?

[quaint star]

What do you mean?

And is what right?

[coarse sparrow]

they asked us to show that the left hand side is the same as the right hand side

normally we have to do both ways

[quaint star]

[coarse sparrow]

but our teacher required only left side

[quaint star]

If the left hand side is the same as the right hand side, then the right hand side is the same as the left hand side

Do you mean you have to show LHS is a subset of RHS?

[coarse sparrow]

it only says to show that they both mean the same thing

so not a sub set

but actually the same set

[quaint star]

Yes, then what you said makes no sense

a = b is the same as b = a

Anyway

X = Y iff X is a subset of Y and Y is a subset of X

So show take the LHS is a subset of the RHS

And then show that the RHS is a subset of the LHS

[coarse sparrow]

ok Lunasong , i got another one more technical , forget about the previous one i sent

hold on

?

please don't tell me its also wrong

[quaint star]

It's wrong

[coarse sparrow]

god

im missing brackets am i right?

[quaint star]

{1} is not an element of P(P(C)) because 1 is not an element of P(C)

Yes

[coarse sparrow]

so i need to add another set of brackets

like

{{1}}

for example

on the first row

[quaint star]

Yes

[coarse sparrow]

on ppc

god damn i knew it

so its gonna be aids

[quaint star]

And it's all a mess because you don't have commas where you should, so it's hard to read

[coarse sparrow]

but pc has to be right

[quaint star]

Yes P(C) is correct

[coarse sparrow]

so {1} is not the same as {{1}}

[quaint star]

No

{1} is the set containing the number 1

{{1}} is the set containing the set {1}

[coarse sparrow]

this should help me with understanding this better

tell me if i got it right

i need to answer True / false

so i said False , True , True , False

[quaint star]

Correct

[coarse sparrow]

nice

one more silly question

so you said to add the brackets

this is the 2nd row

i need to had brackets to the {1} , {2} {1,2} ?

all the way to the end im guessing

[quaint star]

I cannot make out what is written there

You will need one big pair of { } to enclose your whole set. Then for each element, you need another { }, and inside of that should be elements of P(C)

[olive sun]

Can anyone help me, I got 30 mins left
Translation: Prove formally that f(x) = 3x - 2 is injective or not.

[grizzled laurel]

Just insert two different variables in the function

and compare the to functions

f(x)=f(y) gives 3x-2 = 3y-2

3x=3y

x=y

so the function is injective

[candid hollow]

how can i prove that the set {(x,y) s.t x^2+y^2=<1} cant be written as the cartesian product of two sets A and B, where A and B are subsets of the real numbers?

[grim swan]

uh i don’t think it can be

[candid hollow]

yes it cant, and i need to prove that

[grim swan]

oh can’t sorry

misread

ok so

do you have a visual sense of what the cartesian product of two sets looks like?

[candid hollow]

a rectangle?

[grim swan]

yeah pretty much

[candid hollow]

ye i have a vague idea

of how its not possible

[coral raven]

stupid question: ||can't it be polarised||

[grim swan]

@coral raven not in this context

[candid hollow]

i didnt do polar coordinates yet though

[grim swan]

we’re just trying to write the unit circle as a cartesian product in the (x,y)-plane

without some fancy coordinates

[coral raven]

oh okay

well it's not a rectangle

so qed lol

[grim swan]

like unit circle = { (x,y) | x \in A, y \in B}

ok yeah so to make that formal lol

[candid hollow]

yeah thats what i was struggling with lol

[grim swan]

to make the rectangle idea more precise

you know if a \in A, then (a,b) \in A \times B for every b \in B

so like, a point in A generates a line over points in B

and vice versa

[candid hollow]

yeah i can see that

[grim swan]

so for example, if the circle were a cartesian product, (1,0) is a point in the circle, so 1 is in A

[tropic lion]

oh

[grim swan]

and then for every b in B, (1,b) is in the product, and thus the circle

so what’s the problem with that

[candid hollow]

we have a problem at the corners of the rectangle?

idk

[coral raven]

yes

[grim swan]

try and expand on that

how do you know the rectangle has corners

where are the corners

[candid hollow]

wait

to first prove that we have a rectangle

dont we need to prove that the sets A and B are intervals?

[grim swan]

you would yeah

but you don’t need to do that

try drawing a picture btw

This is the picture of what I was describing

[candid hollow]

yeah i had a picture on desmos already

[grim swan]

so I think what you would want to do next is pretty clear from the picture...

if we assume for contradiction the circle is equal to AxB for some sets A and B, we know 1 is in A

since (1,0) is in the circle

can we use that to find a point in AxB that definitely isn’t in the circle?

so you know that AxB = {(a,b) | a in A, b in B}

so there are two things to keep in mind

if (a,b) in AxB, that must mean a in A and B in B

and second, if you have a point a in A, then (a,b) in A x B for every b in B

and similarly, if b in B, then (a,b) in A x B for every a in A

[candid hollow]

am i supposed to find a b for which (1,b) is not in the unit disk?

[candid hollow]

oh lol if i take the point (1,1) it's not in the disk but it's in the rectangle

because the point (1,0) is in the disk, therefore 1 is in A
and the point (0,1) is in the disk, therefore 1 is in B

so (1,1) is in AxB

i was trying to generalize the notion of a corner but i struggled with that, and at the end the answer was really simple...

anyway thanks for the help

[errant bear]

cool

[fluid tendon]

Just need help on 1

I figured out 2 and 3

[opaque fern]

This channel occupied ?

Need help with this

[opaque fern]

<@&286206848099549185>

[crimson jetty]

what is the gcd of these two

are you required to use the euclidean algo?

[opaque fern]

Yea

[crimson jetty]

you can find the bezout coefficients if you use that method

[opaque fern]

Yea exactly what your saying

[crimson jetty]

i'm assuming you were taught the algorithm in a class or something?

are you having trouble with it

[opaque fern]

Yea

The Bezout stuff mostly

@crimson jetty

[crimson jetty]

how did you do euclid's algo

[opaque fern]

Haven’t attempted it yet

But i don’t struggle with it

I can solve it for u rn

If u want

But do it too and see if I’m correct

[crimson jetty]

yup

try it

[opaque fern]

@crimson jetty done

Check Dm or I can send here

[crimson jetty]

oh can u send

[weary tiger]

Formal proofs btw

[crimson jetty]

Check your remainder for the first one

[opaque fern]

100

What did you do?

[crimson jetty]

The question you posted says find the GCD of 3470 and 280, not 3740 as you wrote.

[opaque fern]

Omg

I’m so dumb

@crimson jetty

[opaque fern]

@crimson jetty you around ?

[errant bear]

yeah

[crimson jetty]

this is good

so you can work backwards from here using Bezout's identity, that there exist integer coefficients a and b such that 3470a + 280b = 10.

[opaque fern]

@crimson jetty can you send that part

It’s way to difficult

I won’t get it just hopeless

[crimson jetty]

Use Bezout's identity for each line. I'll do the first one for you as an example:
10 is the remainder here as well as the GCD of 50 and 60, so:
10 = 60 - 50 * 1

Then, we use Bezout's on 50. From the next line up, we have 50 = 110 - 60 * 1 so plugging into our first equation we get:
10 = 60 - (110 - 60 * 1) * 1

[opaque fern]

Would you mind writing it

It’s working backwards right

Can you do that part I’ll just attempt it for this question

There’s another one I need help with also

I flat out don’t know what to do can’t lie

[crimson jetty]

yeah, use bezouts for each line
Then combine like terms by factoring out the 60 that you need for the next line up. so you get 10 = 60 - (110 - 60 * 1) * 1 = 60 - 110 + 60 = 60 * 2 - 110 * 1

Keep using bezouts like this for the rest of the lines until you get the Bezouts coefficients you need.

[opaque fern]

Which are

Can you write what you’ve said on paper

Or some online draw app

@crimson jetty

[crimson jetty]

had to find my phone so made myself a snack. Here's the first few lines, there's only a bit more to do so I'll leave it to you

[opaque fern]

@crimson jetty can you finish it

I did it like this

[crimson jetty]

yayyy awesome!

nice work!

[opaque fern]

It’s correct?

Can you continue with how’s yours would’ve finished

It looked clean and simple

[crimson jetty]

Well you need to write the GCD as a linear combination of 3470 and 280 right? So your problem requests that you find co-efficients a and b such that 10 = 3470a + 280b

So you got 10 = 3470(-5) + 280(62)

[opaque fern]

So that’s the answer

[crimson jetty]

uhh my handwriting's bad but if you insist

[opaque fern]

Gotta sub it in

That says 62 right

[crimson jetty]

yup

[opaque fern]

Way much more simpler to follow

[crimson jetty]

but hey, you got through it once :))

[opaque fern]

Haha

True

How do I lcm

[crimson jetty]

least common multiple?

[opaque fern]

Yea

The last part

[crimson jetty]

well the most obvious way is to factorize both values and then find it that way

but you already have the GCD, and LCM = |3470 * 280| / gcd (3470, 280)

[opaque fern]

So that’s

97160?

[crimson jetty]

mhm

[opaque fern]

Ooo I was correct

971600

/10

[grizzled laurel]

Is this even true?

Can't a simple graph be disconnected, which would mean there could be two vertexes with an odd degree without a path between them?

or am I trippin balls

[quaint star]

It doesn't say there is a path between every pair of odd degree vertices

But each odd vertex has a path to SOME other odd vertex