Bounds on chromatic number when maximum degree is large

For a regular graph with $ n$ vertices and maximum degree $ \Delta$ , it is easy to see that the chromatic number, $ \chi\le\frac{n}{2}$ if $ \frac{n}{2}\le\Delta\lt n-1$ (since a regular graph on $ n$ vertices with maximum degree $ n-2$ is the complete graph with a one factor removed, which will have each vertex non adjacent to a unique other vertex, which could be given the same color, using the handshaking lemma we get that chromatic number of such a graph is $ \frac{n}{2}$ )

How could this fact be applied to bound the chromatic number of any non-regular graph with large maximum degree. Does this fact have a well known name, like Reed’s theorem, or Brooks’ theorem? Thanks beforehand.

Show that a graph has vertices of all even degrees iff its biconnnected components have all even degree vertices

The biconnected components here are all maximal biconnected components.

When I tried solving the problem in the first direction (if the degrees of all the vertices in the biconnected component were even then the degrees of all the vertices in the graph were even), I ran into the problem of that if the degree of every vertex is even, I wouldn’t be able to connect components to them since then the degree of that vertex that connects the component would be odd.

When I went the other direction ( proving that if the degrees of all the vertices in a graph were even, then the degrees of all the vertices in the maximal biconnected subgraphs are all even), I had a similar issue, that if I find a cut edge and remove it from the biconnected components, then the degrees of those vertices incident to the cut edge now become odd if they were originally even.

I’m not sure what to really do at this point, am I missing something?

Does a degree earned in france get me a job in england

I, a 17 year old boy , plan on following my dream of becoming a computer engineer , currently i can only go to university in france , but i really want to live in england . so will a degree i earned in france where everything is taught in french still get me a job in England ? Does the language you were taught with make a difference?Please excuse my poor grammar , i am working on becoming better

Partial differentiation of the general function homogeneous of degree n [on hold]

If $ f$ is homogeneous of degree $ n$ , $ f(tx,ty) = t^{n}f(x,y)$
show that $ f_{x}(tx,ty) = t^{n-1}f_{x}(x,y)$

My proof went a little wrong as follow:
$ u=tx, v=ty \quad f_{x}(tx,ty) = \frac{\partial f(u,v)}{\partial u} \cdot \frac{\partial u}{\partial x}+\frac{\partial f(u,v)}{\partial v}\cdot \frac{\partial v}{\partial x} = f_{u}(u,v) \cdot t$ …….(1)
$ \quad\quad\quad\quad\quad\quad\frac{\partial}{\partial x}(t^nf(x,y))=t^nf_{x}(x,y)$ …….(2)
(1)=(2)$ \qquad f_{u}(u,v)=t^{n-1}f_{x}(x,y)$
$ \quad \quad \quad\quad \,f_{u}(tx,ty) = t^{n-1}f_{x}(x,y)$


On the last line, the footnote on the left side is supposed to be $ x$ , however, I get $ u$ .

Consider a graph G = (V, E) that does not contain any cycle. Show that there is at least one node in G whose degree is at most one


Consider a graph G = (V, E) that does not contain any cycle. Show that there is at least one node in G whose degree is at most one.

I don’t really know how to formalise my logic with this proof. I understand it would be at the endpoint/standpoint of any path (as there are no cycles) but don’t know how to illustrate my logic in a proof like manner. Thank you.

Does this degree 12 genus 1 curve has only one point over infinitely many finite fields?

Let $ F(x,y,z)$ be the degree 12 homogeneous polynomial:

 x^12 - x^9*y^3 + x^6*y^6 - x^3*y^9 + y^12 - 4*x^9*z^3 + 3*x^6*y^3*z^3 - 2*x^3*y^6*z^3 + y^9*z^3 + 6*x^6*z^6 - 3*x^3*y^3*z^6 + y^6*z^6 - 4*x^3*z^9 + y^3*z^9 + z^12 

Over the rationals it is irreducible and $ F=0$ is genus 1 curve.

Numerical evidence in Sagemath and Magma suggests that for infinitely many primes $ p$ , the curve $ F=0$ is irreducible over $ \mathbb{F}_p$ and $ F=0$ has only one point over $ \mathbb{F}_p$ , the singular point $ (1 : 0 : 1)$ .

Q1 Is this true?

Set $ p=50033$ . Then we have only one point over the finite field and the curve is irreducible of genus 1. This appears to violate the bound on number of rational points over finite fields given in the paper “The number of points on an algebraic curve over a finite field”, p. 23.

Q2 What hypothesis am I missing for this violation?

Sagemath code:

def tesgfppoints2():    L1=5*10^4    L2=2*L1    for p in primes(L1,L2):           K.<x,y,z>=GF(p)[]           F=x^12 - x^9*y^3 + x^6*y^6 - x^3*y^9 + y^12 - 4*x^9*z^3 + 3*x^6*y^3*z^3 - 2*x^3*y^6*z^3 + y^9*z^3 + 6*x^6*z^6 - 3*x^3*y^3*z^6 + y^6*z^6 - 4*x^3*z^9 + y^3*z^9 + z^12           C=Curve(F)           ire=C.is_irreducible()           if not ire:  continue           rp=len(C.rational_points())            print 'p=',p,';rp=',rp,'ir=',ire,'g=',C.genus() 

Telling Probability of Point Configurations being in Convex Configuration from Vertex Degree in Planar Euclidean MSTs


Question:

what is the probability that four distinct points in general position in the Euclidean plane are in convex configuration, depending on the number of leaf nodes in their MST?

I assume that a quadruplet of points has a higher probability of being in convex configuration if its MST has two leaf nodes than if it has three, but that that probability is less than 1.

Graphs of maximum degree three

I’m learning an algorithm for graphs of maximum degree three.

My question is: should the graph of that type have at least one vertex with degree three.

For example if the maximum degree of some graph is 2, can we say that this graph is maximum degree three.

Thank you