#Graph Theory Question

60 messages · Page 1 of 1 (latest)

dapper yoke
#

Let V be a stable set of G with size a. Show that degree of G is <= n-a+1

foggy jungleBOT
#
  1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
  2. Wait patiently for a helper to come along.
  3. Once someone helps you, say thank you and close the thread with:
    +close
  4. Feel free to nominate the person for helper of the week in #helper-nominations
  5. Do not ping the mods, unless someone is breaking the rules.
  6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:
dapper yoke
#

We know that, for any graph G, the maximum degree of G is <= 1+ max d(v). Since V is a stable set, it means that no vertex in V is connected to any of the other vertex in V. This means that, for any vertex in V, the maximum degree is n-a, which proves what I need to prove?

#

I don't think it does

#

I feel like the question is a bit incomplete

shy hatch
#

I thought the degree of a graph is the minimal degree for all vertices

#

or is it the maximum degree

dapper yoke
#

Not necessarily, degree just means the number of edges

#

degree of graph is the maximum degree

shy hatch
#

well then it should just be max d(v) no?

dapper yoke
#

Yeah, but we need to prove its <n-a+1

shy hatch
#

that doesn't feel all too true to me to be honest

#

i guess n denotes the number of vertices

dapper yoke
#

pause, i am moronic

#

i am so so so fucking stupid

#

oh my god

shy hatch
#

but if you have a graph with nodes {1, ..., n}, and 1 is connected to everyone else but that's it

dapper yoke
#

no no i am stupid

#

the question is

shy hatch
#

so {2, ..., n} is what you call a stable set right

dapper yoke
#

Let G' be a stable set of G, with size a. Show that G is <=n-a+1 chromatic

#

There is another theorem that shows that G is <=max d<v)+1 chromatic

shy hatch
#

well it would make sense then to show that max d(v) is n-a

#

the problem is that it is not true

dapper yoke
#

Hmm

shy hatch
#

but i mean

#

on the bright side

#

G' can be seen as a single color

#

so that leaves you with n-a nodes to color

#

if each of them has its own color, you have n-a+1 colors

dapper yoke
#

G' is a single color, call that Color C. Removing G', will give us graph G'' with n-a vertices, which can be colored with at most n-a colors

shy hatch
#

so that tells you that n-a+1 is one possible coloring

#

maybe not the best one

#

but it's possible

dapper yoke
#

by adding color C, this means that G is <= n-a+1 chromatic

#

yeah we proved it

shy hatch
#

well that was fast

dapper yoke
#

i know a tiny teeny bit more about graph theory than the combined weight of Monte Carlo, Data Analysis, Linear Algebra and Linear Regression

shy hatch
#

i don't, and I'm supposed to work on a graph neural network

dapper yoke
#

tell me why our professor had us manually calculate the multiplication of a 8x2 matrix with its transpose

#

then had us do it again, except with an 8x3 matrix with its tranpose

#

then had actually find the inverse of X'X and multiply that with X'

shy hatch
#

why manually even

dapper yoke
#

okay with calculators but still

#

LIKE

#

THATS SO MUCH TIME WASTED

#

god

#

you got any good sources on linear programming @shy hatch

shy hatch
#

so good that in fact I barely remember any of it

#

but I think any basic book about optimization should have that

#

my first hit on the net is this

#

it's fairly well structured

dapper yoke
#

ah thank you very much

dapper yoke
#

+close