6 votes

Is Johnson Graph J(N, 2) circulant?

sage is my weapon of choice. It comes with an implementation of the Johnson graph, and so using graph tools in general, delivers further useful information. It may be of interest. The appended code ...
dan_fulea's user avatar
  • 33.2k
5 votes
Accepted

Is Johnson Graph J(N, 2) circulant?

No, the Johnson graph $J(n,2)$ is not a circulant graph, at least not for $n>4$. (Since $J(3,2)$ is a complete graph and $J(4,2)$ is the octahedral graph, they are both circulant graphs.) We can ...
Misha Lavrov's user avatar
3 votes

Maximum number of colors for embedding all colored perfect matchings in the complete graph

This proof is inspired by Patrick's answer. We use a uniformly random coloring of the complete graph $K_{2n}$ with $k=k(n)$ colors, yielding a random colored complete graph $C_{2n}$. For simplicity we ...
Matija's user avatar
  • 3,558
2 votes
Accepted

Island Traveling question

You have a graph, where vertices are islands and edges are (direct) airlines. Its vertices have the following degrees: $21$, $1$, and all the others are $12$. Use the fact that in any graph there is ...
Aig's user avatar
  • 4,381
2 votes
Accepted

Correct Counting of Independent Sets in a Complete Bipartite Graph $(K_{n, m})$

Your first line of reasoning is correct, your second incorrect. Any independent set of a complete bipartite graph $G$, is a subset of one side and one side only. If $S$ is a nonempty subset of the ...
Mike's user avatar
  • 20.5k
1 vote
Accepted

Percolative process distribution not equivalent to coupon collector problem distribution

Even in the general case, if you have a formula $f(n,m,k)$ for the number of arrangements of $k$ elements with a valid top-to-bottom path, the formula $$\Pr[\text{process ends by iteration }i] = \frac{...
Misha Lavrov's user avatar
1 vote

Prove G has a vertex of a degree 1, if G is a connected graph with n > 1 vertices and n - 1 edges.

Using the method of proof by contradiction, if there are no points with a degree of 1, that is, each point has a degree of at least 2. So we have the number of edges is $\frac{\sum_{i}deg(v_{i})}{2} \...
jhzg's user avatar
  • 63
1 vote
Accepted

Proving that graph is class 2

Without loss of generality colour $(10,9)\to1,(10,8)\to2,(10,12)\to3,(10,11)\to4$, then $(9,11)\to2$. This forces $(11,12)\to1,(8,11)\to3,(8,9)\to4$. Now $(9,12)$ touches edges of all four colours ...
Parcly Taxel's user avatar
1 vote
Accepted

How to prove if there is no Hamilton Cycle?

Have a look at vertex $d$. Since a cycle would need to go through $a$ and also $e$, the cycle must pass through vertex $d$ vertically. Similarly looking at $b,f,h$ you conclude that any hamiltonian ...
Cheerful Parsnip's user avatar
1 vote

Does Every Cubic Graph Always Have a 2-factor?

It seems I found a counterexample. In this cubic graph there is no cycle containing $v$. So the graph has no 2-factor.
user966's user avatar
  • 1,939
1 vote

The number of lattice paths from (0, 0) to (2n, 3n) that never go above the diagonal

There is no closed formula for this problem. However the answer can be computed as a simple summation. Theorem 11. The number of words in $D_{3/2}$ with length $5n$ or, equivalently, the number of ...
Smylic's user avatar
  • 6,750
1 vote
Accepted

Constructing infinite 3-connected quadrangulations containing only induced 4-cycles and induced 6-cycles.

Edit: my initial construction was not planar, but I keep it under the line. Take $k$ copies of $H = P_2\times P_3$. Add two adjacent vertices $u$ and $v$. Then for each copy connect $u$ with both ends ...
Smylic's user avatar
  • 6,750

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