# Tagged Questions

8 views

42 views

### Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
64 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 ...
35 views

### How to prove the equivalence of 2 affine spaces given that one is the subset of the other one?

For the sake of completeness, I would like to give you some concepts before asking the questions: For every simplex $S=<<x^{0},x^{1},...,x^{k}>>$ in $\Bbb R^{n}$, denote by $H_s$, the ...
67 views

60 views

### a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
54 views

### Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
27 views

### Probabilistic method in coloring of graph

I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove. There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most ...
92 views

### Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
23 views

### Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
39 views

### A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
25 views

### Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
20 views

### Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
52 views

### Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...