# Tag Info

### 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 ...
• 33.2k
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 ...
• 143k

### 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 ...
• 3,558
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 ...
• 4,381
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 ...
• 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{...
• 143k
1 vote

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} \... • 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 ... • 104k 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 ... • 27.3k 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. • 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 ... • 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 ...
• 6,750

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