# Tagged Questions

65 views
+50

### counting occurence of subgraphs by counting their occurence in larger subgraphs

I have a mental block in fully understanding the following notion. Let $G$ be a graph of order $n$ and $H$ a fixed small graph of order $k \le n$. Suppose that there are $d$ copies of $H$ as an ...
259 views

### How can this technique be applied to a different problem?

Here is the problem (copy and pasted if you don't want to click on the link). Six ants simultaneously stand on the six vertices of a regular octahedron, with each ant at a different vertex. ...
44 views

### Graphs: probability of two vertices, chosen at random, of being connected by a link

If I choose the vertices h and k in a simple graph uniformly, I know the probability of them being joined by an edge is $\frac{2e}{n(n-1)}$ , where: e is the number of edges in the graph, n is the ...
56 views

### Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
36 views

### A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
28 views

### How to solve probability with two conditions (with explanation)?

This is an extension over this question: Inter-causal reasoning: How to solve probability with two conditions? I'm a beginner in probability, and trying to deeply understand what is happening ...
42 views

### How would you incorporate probability into this graph theory problem?

A non-closed path is chosen at random on the complete graph K9. All paths are equally likely. What is the probability that the path contains the edges {23} and {34} given that it is length 6? Given ...
19 views

### Q: Finding probability of connection based on distance?

So, I am new to graph theory and statistics but have encountered a problem that I am not exactly sure how to solve. I have a graph with n nodes and am trying to determine the probability of connection ...
79 views

### Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...