Hot answers tagged

4

You are looking for an $(n,d,\lambda, \lambda)$ strongly regular graph. The normal labelling of the parameters are $(v,k, \lambda, \mu)$, so you are considering the special case where $\lambda = \mu$. There are lots of necessary conditions for the existence of a strongly regular graph. In particular, there are formulas to give the eigenvalues (there are ...


3

Every Directed Acyclic Graph (DAG) on $n$ vertices with the most edges possible is isomorphic to a graph like this: Let $f(n)$ denote the most edges that a DAG $G=(V,E)$ on $n$ vertices can have. Claim: We have that $$f(n)=\frac{n(n-1)}{2}.$$ Moreover, any DAG on $n$ vertices with $f(n)$ edges is isomorphic to the following graph: $$V^*(n) = ...


3

Vertex #7 must be joined to each of the others. This leaves degrees 1,1,2,4,4,4,0 free. At least one of vertices #4, #5, #6 won't be joined to vertex #3. WLOG this is #6. It must be joined to #1, #2, #4, and #5. This leaves 0, 0, 2, 3, 3, 0, 0. But there are no 3 more vertices to join #5 to.


3

The statement given is false, consider the counterexample: cycle $C_5$ of length five, its complement is also $C_5$, thus both are non-bipartite.


3

Yes, it is possible to have non-isomorphic Ramsey graphs. For a census of known Ramsey graphs see this on McKay's web page.


3

Take your vertices to be the mathematicians, put edges bewteen two mathematicians in conflict, and choose one color per hotel. Then the question becomes : can you color this graph such that adjacent vertices are always of different colors ?


3

Given any four points. Draw straight lines between each pair. There are six lines, and one crossing. So drawing straight lines between $n$ points will give $n\choose4$ crossings, although some may coincide. Try to arrange the points so none of the crossings coincide.


3

If you draw $n$ points on a circle and join all of them by lines s.t there is no point that it's intersection of $3$ lines or more, then you have $\binom{n }{4}$ cross points. Because each crossing corresponds to $4$ points. This picture describes what I said for $n=6$


3

I would first prove that every tree has at least one leaf. Added: You have in fact tacitly assumed this in your first bullet point, when you say that every tree on $k+1$ vertices is obtained by adding a vertex to a tree with $k$ vertices. This requires that you be able to remove a vertex from a tree on $k+1$ vertices and still have a tree. This cannot be ...


2

A program like plantri is very fast considering that it can generate exactly one member of each isomorphism class - which is arguably the trickiest part. If you only want a small number of random graphs, and you don't care too much about the uniformity of the random selection, then it seems like an approach like: Generate a random triangulation (T) with ...


2

For a 4-regular graph with $v$ vertices and $e$ edges, the handshaking lemma tells us that $v=2e$. In particular $v$ is even. We have the trivial solution of the empty graph ($v=e=0$), which is vacuously planar and 4-regular. If that is considered cheating, let's exclude it and assume $v\ge 1$. We also could have $v=2$ and $v=4$, but only if we allow ...


2

Hints: (1) How many total edges are there? (2) Can you partition the vertices so that the correct number of edges originate in each set?


2

You are correct. There might be an $NP$-complete problem that can only be translated into Hamiltonian path problem in $\Omega(n^{10})$ time, for instance. In which case an $\Omega(n^{10})$ translation and an $O(n^4)$ solution gives a total time of $\Omega(n^{10})$. The only thing you can be certain of is that the final time is bounded by a polynomial.


2

You can define a bijection between $n$-tuples on $\{0,1\}$ and subsets of an $n$-element set. The basic idea is that the tuple is the characteristic function of the subset, or in other words, we include an element in the subset if the corresponding position in the tuple is non-zero. Define $\phi: \{0,1\}^n \to \mathcal{P}(\{1,2,\ldots,n\})$ as ...


2

HINT: Seat $5$ people around a circular table. Suppose that two of these people are friends if and only if they’re sitting next to each other.


2

jwsiegel has already provided both an asymptotic answer to the original question, and a link to a closed-form solution. I will address the Juan's question in the comments on jwsiegel's answer and Jens's follow-up question in the original post. In answer to Juan's question, "For even n, this is better, but does this work if n is odd?": Nothing in jwsiegel's ...


2

Form a graph with 21 vertices corresponding to the points and edges between pairs of points more than 120 degrees apart. This graph is triangle-free. The number of edges in a triangle-free graph on 21 vertices is (uniquely) maximized for the bipartite graph on 10 + 11 vertices which has 110 edges. Therefore, there are at least ${21 \choose 2} - 110 = ...


1

An edge $e$ crossing $U$ and $V-U$ means that one endpoint of $e$ is in $U$ and another is in $V-U$. For your statement, we can first let $T$ be a minimum spanning tree containing $X$. As stated, let $e$ be an edge with the smallest weight among those that cross $U$ and $V-U$. If $e\in T$, then the statement holds trivially. If $e\notin T$, then ...


1

There are 7 vertices other than $A$ and $B$ in the graph. So, if you want to count the number of paths of length $m+1$ ($1 \le m+1 \le 8$) between $A$ and $B$, you must choose $m$ vertices from those 7 vertices and the arrange them in an order (so you will have a path starting at $A$, going through those $m$ vertices in that specific order and ending at ...


1

You're right that $E[Y]=E[X]$, but I don't quite follow how you calculated $E[Y]$. I'd phrase the probabilistic argument as follows: Your weighted selection of a person can be expressed as uniformly picking a friendship and then uniformly picking one of its two friends. If we now uniformly select a friend of this person, we're uniformly selecting a ...


1

Let $d$ be the diameter of $G$, $n$ the number of vertices of $G$. Let $v,w$ be two vertices realizing the diameter of $G$, i.e. there is a shortest $v,w$-path $v=v_0,v_1,\ldots,v_d=w$ (call it $P$) of length $d$. Note that $P$ has $d+1$ vertices. For the lower bound, note that one vertex can dominate at most three vertices of $P$ (or we find a shorter ...


1

As far as I am aware, the junction tree algorithm can be used as an approximation even in the case that the graphical model is not acyclic, since it creates a factor graph representation of the original model on which belief propagation can be performed (even though the results are only exact if the original model was itself acyclic). This is called ...


1

Hint Show that neither the cycle $C_5$ nor its complement has triangles. P.S. A more interesting problem is to prove that up to isomorphism this is the only possibility. A hint for this is to show that if you have a Graph $G$ which is a counterexample to you statement, then every vertex in $G$ has degree at most $2$ both in $G$ and $\bar{G}$ (and hence ...


1

Take $3$ pentagons. Add an edge between a given vertex and all other vertices belonging to the two other pentagons. To color a pentagon, you need $3$ colors, so to color this graph, you need exactly $9$ colors, but the clique number equals $6$.


1

According to Havel-Hakimi theorem for possible degree sequence in the graph. You given degree sequence $2, 2, 3, 5, 5, 5, 6$ Step$(1):$ Sort the given sequence in decreasing order : $6, 5, 5, 5, 3, 2, 2$ Step$(2):$ Remove degree sequence $6$ and subtract one from only six degree sequence : $ 4, 4, 4, 2, 1, 1$ Step$(3):$ Sort the given sequence in ...


1

Here is my attempt at a Python implementation (2 or 3) of gf3 and gf5. I am only using builtin libraries, so hopefully that will encourage others to play with this. My results agree with the above for $1\leq n \leq30$ and $n=50$ but this will obviously need verification. The performance of gf5 is not great, over 400 seconds for $g_{55}(u)$ alone. I ...


1

There are two kinds of matrices most often used to represent simple undirected graphs, adjacency matrices and incidence matrices. [Their variations for graphs that allow loops/self-edges, multi-edges, and/or directed edges are common, but we mostly avoid discussing them here.] The adjacency matrix for a bipartite graph is mentioned already in the Question. ...


1

I'm not too sure what the etiquette is on Math SE regarding answering old questions but I stumbled across this question and felt it would be good to drop an answer for future users that happen to ask the same question in the future. Anyways, I'm going to do the particular case when $\delta(G) = 3$ and show that there exists a path of at least length 3. This ...


1

Let $G$ be a graph on 6 vertices. Pick one vertex $v$, and think about the edges connected to it. There are five other vertices, so either there are at least 3 edges incident to $v$ in $G$, or there are at least 3 edges incident to it in the complement $G^c$. Now consider the three vertices that $v$ is connected to in either $G$ or $G^c$. Think about ...



Only top voted, non community-wiki answers of a minimum length are eligible