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.
25,001 questions
2
votes
2
answers
205
views
Coloring a graph with K-colors
Given a graph, I wish to try and color it with the minimum number of colors (0,1...k).
Each 2 connected vertices must have different colors.
I proposed the following algorithm - Initialize an array of ...
- 23
3
votes
1
answer
47
views
Prove that the chromatic polynomial of $n$-vertex graph has no real root larger than $n-1$
Let $G$ be a graph on $n$ vertices. If we have $k$ colors where $k > n-1$, then obviously we can color all the vertices of $G$ with distinct colors so that we have a proper coloring using $k$ ...
- 33
-1
votes
1
answer
33
views
Justification for Definition of Directed and Undirected Graph
It is commonly known that directed graphs are defined as a double $G_d:=(V,E)$ such that $E \subseteq V^2$, and that undirected graphs $G_u:=(V,E)$ such that $E \subseteq \left\{ \{a,b\}\Big\vert a \...
- 69
2
votes
1
answer
98
views
Minimum number of forbidden cells for a unique loop on $m \times n$ grid
I recently asked about the minimum number of black (forbidden) squares needed to guarantee a unique "loop" cycle on an $n \times n$ grid. It seems natural, then, to consider $m \times n$ ...
- 5,173
-2
votes
0
answers
90
views
Tower of Hanoi Solution Via Counting
I am trying to find an alternative understanding/proof why the Tower of Hanoi can be completed in $2^n-1$ steps. I understand this to be true via recursion.
However, I’m seeking an approach that ...
- 28
0
votes
0
answers
27
views
The triangulations of one graph all come from the other two [closed]
In graph theory, a triangulation means adding edges to make a graph maximal planar. The following picture is denoted by $G$.
The following picture is $G_1$.
The following picture is $G_2$.
Now ...
- 1,757
6
votes
1
answer
81
views
Finding $\lim_{n \to \infty} \frac{l(n)}{n^2}$ for minimal vertex coloring satisfying a property for all $k \times k$ sub-squares
I am working on the following grid coloring problem and am stuck on finding the general form of $l(n)$.
The Problem
Some of the vertices of the unit squares of an $n \times n$ chessboard are colored ...
- 296
2
votes
1
answer
86
views
Are bounds known on the number of quadrilaterals (or 4-cycles) of the putative Conway 99 graph?
The putative Conway $99$ graph is a defined as an undirected graph with $99$ vertices, in which each two adjacent vertices have exactly one common neighbour, and in which each two non-adjacent ...
- 2,441
1
vote
1
answer
48
views
Does there exist a class of graphs with superpolynomial but subexponentially many maximal cliques?
Let $G$ be a finite simple graph on $n$ vertices, and let $\kappa(G)$ denote the number of maximal cliques of $G$.
It is known that there are graph classes with exponentially many maximal cliques. For ...
- 3,376
1
vote
0
answers
38
views
The permutation model is an expander with high probability
In the book Computational Complexity: A Modern Approach you can find the following problem
this is actually a multi-graph with loops. Their definition of expander and a hint are attached below
My ...
- 4,768
0
votes
0
answers
21
views
Cycle between ranks of partitions in a box
Let $P(n, k)$ be the poset of partitions in the $k \times n$ box under diagram containment. Explicitly, $P(n, k) = \{(\lambda_1, \ldots, \lambda_k) \mid n \geq \lambda_1 \geq \cdots \geq \lambda_k \...
- 12.2k
2
votes
1
answer
50
views
Minimum nodes in a 36 edged shape with non-crossing edges and coloured nodes, with no similarly coloured nodes touching
I've been struggling and have managed to build a couple of networks with relatively low nodes but the correct edges but then I can't colour them correctly. I noticed an observation with lower numbers ...
- 23
0
votes
2
answers
60
views
Maximum number of non-crossing edges in a 7-node network, such that nodes can be three-colored without same-colored nodes being connected
I've been struggling through this and created a bunch of options where 12 work such as alternating colour 1 and 2 around the edges and having colour 3 in the middle, but I have a suspicion that there ...
- 23
8
votes
0
answers
154
views
What's the pattern behind the algorithm of repeatedly taking a number and subtracting its reverse digits?
The algorithm is quite simple. Let's start with some definitions.
Take an integer $k$ of length $N$ we can denote its digits from left to right as $k=k_0k_1... k_{N-1}$.
Now let $k_{rev}$ be the ...
- 205
1
vote
0
answers
28
views
Weighted fractional variant of Hall's marriage theorem
Let $G = (V,E)$ be a graph. Let $w: V \to [0,1]$ be a function that assigns a weight to each node. A fractional matching in $G$ is a function $f: E\to [0,1]$ such that, for each node $v\in V$, the ...
- 11.6k
10
votes
1
answer
326
views
Upperbounds on the maximum independent set for Conway's 99 Graph (if it exists).
I am just curious about Conway's 99 Graph Problem, it asks:
Does there exist a graph where every edge belongs to a unique triangle and every non-edge belongs to a unique quadrilateral?
For purposes ...
- 3,652
2
votes
1
answer
91
views
Can Sumner’s theorem also be proved using the Tutte's 1-factor theorem?
The classical result, known as Sumner’s theorem, shows that every connected claw-free graph of even order has a perfect matching(i.e., 1-factor). One of the proofs can be found in Sumner’s original ...
- 2,765
7
votes
1
answer
270
views
What is the number of connected components of this graph?
Consider natural numbers $e_1 < e_2 < ... < e_k <n$. Define the graph $G$ to have the vertex set $V= \{1,\dots, n\}$ and edge set $E = \{(a,b)\in V^2 \: |\: \exists j=1,\dots, k: a = b\pm ...
- 660
1
vote
1
answer
85
views
Olympiad Graph Theory Problems related to Trees
I was wondering if there are any good resources that collect Olympiad problems in graph theory, especially those involving trees. If not, I’d love to hear about some of your favorite Olympiad problems ...
- 481
1
vote
1
answer
51
views
In a simple graph $G$ with $7$ vertices $v_1,\ldots,v_7$, if $\deg v_i=i$ for $i=1,\ldots,6$, find $\deg v_7$.
Let $G$ be a simple graph with $7$ vertices $v_1,\ldots,v_7$. If $\deg v_i=i$ for $i=1,\ldots,6$, find $\deg v_7$.
Attempt: Let $\deg v_7=d$. By the handshaking lemma, we obtain $\sum\limits_{i=1}^{7}\...
- 2,767
6
votes
1
answer
360
views
How should the notion of "cycle" be defined if we want the definition to capture what we actually mean by such a thing?
According to Wikipedia, a cycle (in graph theory) is a non-empty trail in which only the first and the last vertex are equal, but I’m sure this isn't what we normally mean by that notion. It seems ...
- 1,037
0
votes
1
answer
40
views
Are maximal subgraphs related with posets?
I read that given a graph $G$, we say $S$ is a maximal subgraph of $G$ with property $p$ if for all $S'$ contained in $G$ which strictly contain $S$, then $S'$ does not have property $p$.
I was ...
1
vote
1
answer
61
views
Find a non-trivial upper bound on the number of edges of a planar graph with $t$ degree-4 vertices incident to non-triangular faces?
A well-known result states that any planar graph of order $n \ge 3$ has at most $3n - 6$ edges, and this upper bound is attained if and only if every face boundary forms a triangle.
Now we impose an ...
- 2,765
4
votes
1
answer
195
views
Subset sums where I have to ensure multiple different sums.
Base problem is "What is the smallest c such that every subset of S = {1, 2, ..., 100} with c elements contains at least one pair whose sum is a perfect square?"
Using disjoint pairs {1,99},{...
- 43
1
vote
1
answer
51
views
Use the sampling argument to prove density Szemeredi (supersaturation) problem
This Exercise comes from Graph Theory and Additive Combinatorics (Yufei Zhao). I have tried for several days but end up with no idea.
Exercise 1.3.7. (Density Szemeredi). Let $k\geq 3$. Assuming ...
- 105
1
vote
1
answer
37
views
Does a simple graph really have to be $2$-connected if for every triple $(x,y,z)$ of distinct vertices, there is an $x,z$-path through $y$?
Reportedly this is problem 4.2.8 in “Introduction to graph theory” by West.
Prove that a simple graph $G$ is $2$-connected if and only if for every triple $(x,y,z)$ of distinct vertices, $G$ has an $x,...
- 1,037
1
vote
1
answer
74
views
If the subdivision of a graph $G$ is Hamiltonian, is $G$ Eulerian?
I’m reading “A first course in graph theory” by Chartrand and Ping Zhang and I’m stuck on proving (or disproving) the following statement:
Problem: The subdivision graph of a graph $G$ is that graph ...
- 131
1
vote
1
answer
72
views
What is a worst case graph for this streaming algorithm?
Consider the following streaming algorithm for maximum matching in a weighted graph.
...
- 779
1
vote
1
answer
93
views
Show that there is no Hamilton cycle in the graph below which contains exactly one of the edges e1 and e2.
Show that there is no Hamilton cycle in the graph below that contains exactly one of the edges e1 and e2.
This is what I tried: I deleted one of the edges , $e_1$ and $e_2$, without loss of ...
- 23
1
vote
0
answers
48
views
Am I right if I claim that the graph $K_1$ is connected but not 1-connected?
$K_1$ is connected, I think, as for any two vertices $a$ and $b$ in the graph, those must both be equal to the graph's only vertex, which makes that a path (of length zero) from $a$ to $b$.
However, ...
- 1,037
0
votes
0
answers
69
views
Does this path on $\mathbb{Z}\times\mathbb{Z}$ separate two points?
I am currently working on a problem which I managed to reduce to solving the following:
Let $X = \mathbb{Z}\times\mathbb{Z}$, where we'll say an element $(x,y) \in X$ is adjacent to elements $\{(x-1,y)...
- 355
2
votes
2
answers
117
views
What is the relation between matchings and edge coverings?
Let $G$ be a graph with no isolated vertices.
A set of vertices in $G$ is called
independent if no two vertices in the set are incident on the same edge;
vertex cover if every edge is incident to ...
- 7,029
0
votes
1
answer
65
views
If a graph has at least 3 vertices (A,B,C) and there are 2 paths between A,B as well as 2 paths between B,C prove there is/n’t 2 paths between A,C
An undirected graph G contains at least 3 vertices (A,B,C). A and B have two edge-disjoint paths; B and C also have two edge-disjoint paths. Can I conclude that A and C also have two edge disjoint-...
- 11
4
votes
1
answer
69
views
Does Serre's property $FA$ imply property $F\mathbb{R}$?
In the area of geometric group theory, a group $G$ has Serre's property $FA$ if any action on a tree must have at least one fixed point.
However, this article of Culler and Vogtmann defines a property ...
- 43
0
votes
0
answers
25
views
How to know if a complete graph can be divided in triangles such that no triangle shares a side? [duplicate]
Let $n$ be a positive integer. Let $K_n$ be a complete graph. My question is, how can I know if $K_n$ can be decomposed into triangles (meaning there is a set of subgraphs of $K_n$, each of which is ...
0
votes
1
answer
70
views
How can I practically identify the 3-manifold whose triangulation is given by the clique complex of a graph?
Context: I like local graphs (neighbourhood graph of each vertex is isomorphic).
I like to look at these graphs' clique complexes, i.e. moving from a combinatorial to geometry and topology view and vv....
- 2,441
0
votes
0
answers
40
views
Properly Discontinuous Action of a Group on a Tree
Exercise 10.33 in Rotman's "An Introduction to Algebraic Topology" asks us to prove that
Let $G$ be a group. If there exists a tree $T$ on which $G$ acts properly (discontinuously, in the ...
- 1,443
16
votes
3
answers
1k
views
Minimum # of black squares to guarantee uniqueness of loop visiting all white squares
I believe context will help before the statement of the problem. I was asked
In the picture below, can you find a closed, non-intersecting loop visiting every white square exactly once? (If you do, ...
- 5,173
6
votes
1
answer
107
views
Delete edges to make a graph bipartite
I have troubles with the following problem:
Exercise 1.1.9*. Let $G$ be an $n$-vertex graph with $\lfloor n^2/4\rfloor -k$ edges (here $k \in \Bbb{Z}$) and $t$ triangles. Prove that $G$ can be made ...
- 105
2
votes
2
answers
182
views
Question about a specific graph theorem
I have been told to prove the theorem that a graph $G$ has an independent set of size at least $k$ containing vertex $v$ iff $G-N(v)$, where $N(v)$ is the set of vertices containing $v$ and all of its ...
- 29
5
votes
0
answers
301
views
problem from ongoing contest (USAMTS Year 37 Round 2)
problem from ongoing contest (USAMTS Year 37 Round 2).
5
votes
0
answers
184
views
Does Birkhoff-von Neumann's Theorem easily imply Hall's Marriage Theorem or equivalent?
The following is a collection of combinatorics theorems commonly refereed as "equivalent" due to one being easily derived from another.
Theorem (Hall).
A finite bipartite graph $G = (A\...
- 7,029
2
votes
1
answer
39
views
For fixed $n, m$, are all almost-regular graphs isomorphic?
As title states, I'm curious whether there can be two "distinct" $(n, m)$-almost-regular graphs $G, G'$ such that the amount of vertices with degree, say, $d$, and the amount of vertices ...
- 972
2
votes
0
answers
17
views
Is it true that a graph has a fractional perfect matching if and only if $i(G\setminus S)\leq |S| $ for all $S\subset V(G)$?
Is it true that a graph has a fractional perfect matching if and only if $i(G\setminus S)\leq |S| $ for all $S\subset V(G)$? And why?
Here $i(G\setminus S)$ denotes the number of isolated vertices of ...
- 1,112
0
votes
0
answers
39
views
Limitations of a graph invariant
Take a colored complete $K_n$ graph. Here is a "triangles" invariant:
Let $C(e)$ denote the color $c$ of an edge $e$.
For all nodes $i$, loop over $j,k$ and fetch the colors of the edges $...
- 833
4
votes
1
answer
118
views
Are adjacent triangular cells in 3-regular planar map possible?
I come from a very non-graph background, but I'll do my best to properly pose the question:
I have a 3-regular graph where the faces are simple polygons (they only meet along edges or vertices, each ...
- 143
1
vote
0
answers
48
views
General book graph
In graph theory, usually a book graph $B_p$ implies $p$ 4-cycles $(C_4)$ sharing an edge. I saw in wikipedia that this could also be called a quadrilateral book and there's a variant called triangle ...
1
vote
1
answer
70
views
Question about Lemma 3.1.2 in Diestel's Graph Theory.
In lemma 3.1.2 of his book, the following is stated:
Lemma 3.1.2. Let G be any graph.
(i) The cycles of G are precisely the cycles of its blocks.
(ii) The bonds of G are precisely the minimal cuts ...
- 59
0
votes
0
answers
103
views
Minimum steps to cut a truss
Motivation
While I was looking at the method of sections to find the forces in the members of a truss in engineering mechanics, I had a question about the minimum amount of calculation required to ...
- 113
2
votes
0
answers
24
views
Unique (connected and simple) graphs that are locally Möbius ladder graphs
It is easy to see that $K_5$, the complete graph with 5 vertices is local and that the local graph (open neighbourhood definition) of $K_5$, i.e. the graph consisting of the neighbours of a vertex and ...
- 2,441