# Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

23,508 questions
Filter by
Sorted by
Tagged with
7 views

### Bounds on chromatic number in terms of chromatic numbers of subgraphs.

Suppose we have a graph G of the form $G = G1 \cup G2$, and graphs G1 and G2 are defined by $V(G1) = V(G2)$. How can we describe the dynamics of the chromatic number of G in relation to the chromatic ...
39 views

### Corollary of Ore's Theorem

"Theorem (Ore; 1960) Let G be a simple graph with n vertices. If $$\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n$$ for every pair of non-adjacent vertices v, w, then G is Hamiltonian." ...
12 views

### Graph theory proof : graph with vertices of degree 4

Let $\mathscr{G}$ be a graph with $deg(v) = 4$ for all vertices. The graph has no loops. Proof that you can colour the edges with $2$ colours such that every vertex lies on 2 edges of one colour and ...
18 views

### What does the proportion between the mean size of the clusters and the number of clusters mean in the site percolation model?

I am trying to find a way to quantify the degree of clustering in the site percolation model for a planar lattice, such as a square. I am considering taking into account the ratio between the average ...
16 views

78 views

### The Ant's Mathematical Quest: Navigating an Infinite Tree of Odd Numbers

Enigma: In a mathematical tree, an ant begins at its home, represented by the number 1, and seeks to find a grain of rice placed upon any odd-numbered leaf. This is no ordinary tree: the branches are ...
131 views

### Let G be a connected graph in which every vertex has degree three. Show that if G has no cut-edge then every two edges of G lie on a common cycle.

"Let $G$ be a connected graph in which every vertex has degree three. Show that if $G$ has no cut-edge then every two edges of $G$ lie on a common cycle." I have an idea for this proof but I'...
21 views

### Find two edge-disjoint spanning trees in $H_4$, the 4-dimensional hypercube. Draw $H_4$ and the trees. [closed]

Your help will be highly appreciated.
31 views

### Let $G = (V, E)$ be a bipartite graph. Show that we must have $|A| = |B|$ [closed]

Let $G = (V, E)$ be a bipartite graph with parts $A$ and $B$, hence, $V=A\cup B$. Assume that the degree of every vertex of $G$ is precisely $r$ (here $r$ is a positive integer). Show that we must ...
37 views

### Showing the isomorphism between (the geometric lattice)$\pi_n$ and the lattice $\mathcal{L}(M(K_n)).$

Here is the question I am trying to solve: Show that the lattice of flats of $M(K_n)$ is isomorphic to the partition lattice $\pi_n$. Definition: $\pi_n$ is the set of partitions of $[n]$, partially ...