Questions concerning connectivity of graphs

Question

So, we have been working with graphs for a while now and the profesor has handed out some questions for us to think. There are 3 of them that caught my attention:

May the graph with 4,3,3,3,3,1,1 degree sequence exist? If so, can we assure it is connected?

May the graph with 4,3,3,3,3,3,1 degree sequence exist? If so, can we assure it is connected?

I thought you couldn't know much with only the degree sequence, but it turns out that this last graph exists and is in fact connected. Why is this? The last interesting question was: Let G be a graph such that every two edges are adjacent. Prove that if the number of edges is 28 the number of vertices is greater than or equal to 29.

Answer 1

Hints. The connected component of the second graph must have at least four vertices (why?).

Let us denote the third graph by $G$:

1. we can assume that $G$ has no isolated vertices;

2. then $G$ is connected;

3. then $G$ has no triangles;

4. then exactly one vertex of $G$ has degree greater than 1.

Answer 2

I'll answer the first part of your question.

Define $[n]:=\{1,...,n\}$. Let $G=(V,E)$ with $|V|=n$.

The question that asks, given a degree sequence $s_1\ge ...\ge s_n$, whether there exists a graph with these degrees is called graph realization problem.

Let's instead view degree sequences as degree functions $f:[n]\to\{0,...,n\}$. That is, if $s_1\ge ...\ge s_n$ is a degree sequence, the corresponding function is $f(1)=s_n,...,f(n)=s_1$.

Now, a graph is connected if and only if for all partitions of $V$ into non-empty sets $A,B$ there is an edge between $A$ and $B$.

It is possible to test the above using for example the Erdős–Gallai theorem.

A simpler, but only sufficient condition for a graph with degree function $f$ to be connected is this: $$\forall i\in[\lfloor n/2\rfloor]: f(i)\ge i$$

This condition assures us that no matter how we partition $V$ into $A$ and $B$, if the smaller of the two sets has $k$ elements, then it contains a vertex with degree $k$, so there has to exist an edge between $A$ and $B$.

Answer 3

I'm guessing "degree sequence" meaning just the degrees of the vertices, without any other meaning. If my guess is wrong, then downvote my answer, because it's gibberish then.

I ALSO ASSUMED YOU ARE TALKING ABOUT SIMPLE GRAPHS! Please let me know if it must not be simple.

I would like to answer the first one by an example. Consider 2 disjoint graphs, $K_2$, and a square. The square have degree sequence 2,2,2,2. Now take an extra vertex, connect it to all of the vertices in the square. The new vertex has degree 4, the old vertices of the square now have degrees 3,3,3,3. That is, we have 2 disjoint graphs with degree sequence 4,3,3,3,3,1,1.

About the second question, existence is a yes! Check the picture below (the middle intersection is not a vertex).

About whether or not it must be connected, notice that all the vertices with degree 3 must be a part of a connected component with at least 4 vertices. We have 5 vertices with "relatively big" degree, 4,3,3,3,3. We know at least one component must have 4 or more vertices.

1. If we have a component with 4 vertices, then we have {4,3,3,3},{4,3,3,1}, {3,3,3,3},{3,3,3,1} as one of the components. The first and second one is flat out impossible. The third one is possible, but that leaves us a a vertex with degree 4 and a vertex with degree 1 as the other component, so impossible. The fourth one is impossible.
2. If we have a component with 5 vertices, then we have an isolated vertex with positive degree!

Thus we can conclude it must be connected. But this is brute force, perhaps there is a more sophisticated way...

About the extra question, I claim that the graph is a star. An equivalent statement is that all the edges share a common endpoint.

Proof: Suppose we have 2 "cluster of intersections" (or minimum size of vertex cover is 2), vertices $x$ and $y$. That is, all edges either end at $x$ or at $y$. We can have edges {$x$,$y$}, {$v,x$},{$v,y$}. So, a triangle is fine, it fulfills that all edges are adjacent. What if we want to have the 4th edge? Out of the 3 element set {$x,y,v$}, the 4th edge must pick one of these (can't be both, already exist such an edge! Also can't pick none of the the 3, because then it would be disjoint!). WLOG, suppose the 4th edge is {$v',x$}, but it would then be disjoint to {$v,y$}. Obviously we can't have even more "cluster of intersections".

Then, what star graph have 28 edges? A star graph with 29 vertices! We can then add arbitrarily many isolated vertices.