Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
8 views

weighted matroid intersection theorem

I am trying to prove the result in Section 6 of this lecture note. It just says the proof is similar to the non-weighted version without giving it. (A same non-weighted version proof is here, which ...
Connor's user avatar
  • 2,045
0 votes
0 answers
15 views

Well-founded Relation on infinite DAGs

A well-founded relation on set $X$ is a binary relation $R$ such that for all non-empty $S \subseteq X$ $$\exists m \in S\colon \forall s \in S\colon \neg(s\;R\;m).$$ A relation is well-founded when ...
MB7800's user avatar
  • 51
1 vote
1 answer
28 views

Maximum weight edge in a cycle and Minimum Spanning Tree

Consider G a simple, connected, undirected graph. I know there exists a property called cut property, which states that for a given cut $(S, G-S)$, if an edge $e$ crossing that cut from $S$ to $G-S$ ...
piero's user avatar
  • 426
0 votes
0 answers
7 views

In a simple weighted planar graph, find the shortest (in terms of total length) set of closed walks that cover all shortest paths

Consider a simple planar graph $g$ embedded in the 2D plane with weights corresponding to Euclidean distances, and let $P$ be the set of all its shortest paths $p$. I want to find a set $W$ of at most ...
schmuelinsky's user avatar
0 votes
0 answers
8 views

strongly connected directed graph with exactly one indegree per vertex proof

How can we prove in a strongly connected directed graph with exactly one indegree per vertex that each vertex will be reached, and the cycle will return to the starting point?
Loren's user avatar
  • 1
0 votes
0 answers
21 views

cut metric and lp duality

I would like to show that the following two statements are equivalent. Let (𝐴,𝑑) be an 𝑛 -point metric space and 𝐵 a set of (𝑛C2) pairs of points of 𝐴 . Then ∃𝑡≥1 , an integer 𝑚 , and an ...
Eclipse's user avatar
3 votes
2 answers
231 views

Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?

Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6? I know, Theorem: In a connected planar graph where each vertex has the same ...
Glo's user avatar
  • 69
2 votes
1 answer
290 views

Can a connected planar graph have 10 vertices and edges? is this possible?

Can a connected planar graph have 10 vertices and edges? is this possible? Using Euler’s formula, $V − E + F = 2$. $10 − 10 + F = 2$, Therefore $F = 2$. Do I also need to use this formula: $2E$ $\geq$ ...
Glo's user avatar
  • 69
2 votes
1 answer
31 views

Proving the chromatic number of this graph is $4$

I was required to prove that the following graph $G = (V, E)$ satisfies $\chi(G) = 4$: Since $C_5 \subseteq G$ we have $\chi(G) \geq 3$. Since $G$ is connected and $\Delta(G) = 5$, Brook's theorem ...
lafinur's user avatar
  • 3,344
1 vote
1 answer
37 views

matroid intersection and graph orientation

I am reading this lecture note and feel confused about the Theorem 6.2 there. Using the notation in Section 6.1.3, we should prove that for any $U\subseteq A$, $$r_1(U)+r_2(A\setminus U)\ge |E|.$$ I ...
Connor's user avatar
  • 2,045
1 vote
1 answer
47 views

Distinct and valid parent arrays of a tree

A tree has 10 nodes, numbered from 1 to 10, and its parent array v = {0, 1, 1, 2, 2, 3, 3, x, y, z}. How many distinct and valid parent arrays can be formed by giving values to x, y and z? My (wrong?) ...
Leon's user avatar
  • 33
1 vote
1 answer
38 views

$G$ hamiltonian iff $H^2$ is hamiltonian

Let $G$ be a graph on the vertex set $V = \{v_0, \ldots, v_{n-1}\}$. Construct $H$ as the graph on vertex set $\{v_0, \ldots, v_{n-1}, u_0, \ldots, u_{n-1}, w_0, \ldots, w_{n-1}\}$ with $$ E(H) = E(G) ...
mNugget's user avatar
  • 493
0 votes
1 answer
35 views

Maximize happiness in seating plan with cliques

Parameters of the problem: There are $x$ tables with capacity 8, $y$ tables with capacity 6, and $z$ tables with capacity 4. There are $8x+6y+4z$ people to seat. There exist cliques that wish to ...
Bryan K.'s user avatar
0 votes
0 answers
25 views

Prove that for complete biclique Ki,j that ∆(Ki,j) = χ′(Ki,j).

I am trying to prove it by contradiction. Proof: "Assume that ∆(Ki,j) != χ′(Ki,j) for a complete biclique (Ki,j). If ∆(Ki,j) > χ′(Ki,j), it implies that the minimum number of colors needed to ...
Banon Bhuiyan's user avatar
0 votes
1 answer
16 views

edge-transitive but not vertex-transitive graph is bipartite [closed]

How to prove a graph that is edge-transitive but not vertex-transitive is bipartite? I think about using odd cycles if it not a bipartite graph, but I cannot establish its link with edge/vertex ...
Junya's user avatar
  • 19
3 votes
2 answers
96 views

Sum of critical graphs is critical

Let $G_1$ and $G_2$ be $k_1$ and $k_2$ critical respectively. That is $\chi(G_1) = k_1$ and $\chi(G_2) = k_2$ and the removal of any vertex or edge reduces the chromatic number. I am trying to prove ...
mNugget's user avatar
  • 493
1 vote
1 answer
26 views

Maximum number of edges such that $\nu(G) < \frac{n}{2}$

Given an even integer $n$. I want to find the largest number of edges in a $n$-vertex graph such that the matching number is strictly less than $\frac{n}{2}$. I believe that the maximum is obtained by ...
mNugget's user avatar
  • 493
1 vote
0 answers
14 views

What class of subgraphs of the $n$-hypercube graph characterizes the region graphs of arrangements of $n$ hyperplanes in $\mathbb{R}^d$?

I am looking for a reference that answers or at least discusses the question in the title. I browsed Sergei Ovchinnikov's book "Graphs and Cubes" and several lecture notes on hyperplane ...
axelniemeyer's user avatar
0 votes
0 answers
34 views

Show that equi-bicolored tree has at least one leaf of each color

I need to solve the following problem using induction: Every equi-bicolored tree has at least one leaf of each color. Equi-bicolored means that a tree is 2-colored and has the same number of vertices ...
Victor Feitosa's user avatar
0 votes
1 answer
35 views

How Many Unique Ways Can I Color a Regular Hexagon Using 3 Colors Without Neighboring Vertices Sharing the Same Color? [closed]

I'm trying to solve a problem involving coloring a regular hexagon. Specifically, I need to color each vertex green, red, or blue, with the restriction that no neighboring vertices can have the same ...
Ruchin's user avatar
  • 17
0 votes
1 answer
14 views

Show that a regular class 1 graphs cannot contain an unmatchable edge.

We call an edge in a graph unmatchable if it is not contained in any perfect matching. Then how to show that a regular class 1 graphs cannot contain an unmatchable edge? I know th definition of ...
Nekomiya Kasane's user avatar
1 vote
1 answer
35 views

Automorphism group of d-regular trees

A (infinite) tree is $d$-regular if every vertex has $d$-many neighbors. Needless to say, the tree will be infinite in size. My question is about the automorphism group of the said tree, $\mathrm{Aut(...
Sajid Bin Mahamud's user avatar
0 votes
0 answers
10 views

Steiner trees and their topologies

As I could understand, the Steiner topology is obtained by the structure of a non-degenerate minimum Steiner tree which solves the Steiner tree problem. That means, the corresponding Steiner tree has ...
Oshan Maduwage's user avatar
0 votes
0 answers
38 views

Extremal function definition problem while proving $ex(n, P_4) = n+1$.

I'm struggling to prove that $ex(n, P_4) = n+1$, this exercise was assigned to us during the class, where with $P_4$ i mean the path on $4$ vertices (indicated with $P^3$ in some books). I've set up ...
Lorenzo Arcioni's user avatar
2 votes
1 answer
25 views

Proving lower bound for the length of a cycle in a 2-connected graph.

I'm trying to prove that every 2-connected graph $G$ has a cycle $C$ such that $\vert C\vert\ge\text{min}(\vert G\vert,2\kappa(G)$ where $\kappa(G)$ is the connectivity of the graph (may be larger ...
Math 2tor's user avatar
  • 176
1 vote
1 answer
27 views

Terminology for a "semi-bipartite" graph strucure (graph theory)

Let $G$ be a finite graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that a vertex in $V$ can be connected to any vertex in $G$, but a vertex in $U$ can be connected only to ...
DYZ's user avatar
  • 111
2 votes
3 answers
95 views

Given $n$ equivalent statements. What is the most amount of implications one can use to prove that all statements are equivalent?

I found this question interesting but have no idea how to go about it. I suspect one can use some advanced graph theory, but I am not particularly strong in that area. Here is the question: Given $n$ ...
mNugget's user avatar
  • 493
0 votes
0 answers
19 views

Sample a random subgraph from an undirected, unweighted graph, what's the probability of "every two nodes's distance is at least 3 in the subgraph"? [closed]

This may be a problem in sampling theory or graph theory. I have done many research but I still didn't find valid solutions. I know a simple random sample is representative of the population. Now I ...
ChS's user avatar
  • 1
1 vote
0 answers
45 views

Maximizing the number of colors so that every subgrid contains all colors

Consider an $n\times n$ grid. Define the set $S$ as subgrids shapes which includes all $(i,j)$ pairs so that $i\times j=n$. eg: we can take $i=1, j=n$ which is a row shape structure and it belongs to ...
Happypantsdw's user avatar
2 votes
1 answer
41 views

Tournament between 10 players, maximum number of games, also minimum number of wins to get 4th place

Say we have a video game tournament, in which 10 gamers play all against each other. Assume that each match ends in one person winning and another losing, no draws. What is the maximum number of ...
Computers's user avatar
  • 337
2 votes
0 answers
41 views

Asymmetric graph with with increasing depth of asymmetry

Let $G = (V,E)$ be a graph. Define the depth of asymmetry as $|V| - d$, where $d$ is the rank of the largest non-trivial partial automorphism of a graph $G$. Can we find a construction such that $d$ ...
Eauriel's user avatar
  • 21
2 votes
0 answers
25 views

consistent vertex configurations for Archimedean tiling

I am trying to find if there is a simple rule for vertex configurations $n_1.n_2\ldots n_k$ that define Archimedean tilings (equivalently called uniform/semi-regular/vertex-transitive tilings). In ...
Tomáš Bzdušek's user avatar
0 votes
0 answers
29 views

Is there an algorithm out there to make a maximal planar graph, either from nothing or from a given graph?

I am currently working on creating a program to create a maximal planar graph (a graph that only has faces that are surrounded by 3 edges, including outbound faces). I was wondering if such an ...
HummingCloud's user avatar
-1 votes
0 answers
18 views

Algorithms & Datastructures: Depth-First Search (DFS) and Breadth-First Search (BFS) Space Optimizations [closed]

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
Michel H's user avatar
  • 300
0 votes
1 answer
20 views

Setting sampling probability when sparsifying a non-negative weighted graph

Given a set of $mn$ non-negative edges, with what probability should one keep every edge $w_{ij}$ if we want $\sim pmn$ non-zero weights in our sparsified and every edge is sampled with a probability ...
meowcaroons's user avatar
4 votes
1 answer
124 views

Permutations of 10 players within 2 Badminton courts: Covering $10$-vertex complete graph $K_{10} $ by two disjoint $K_4$

I am facing this everyday problem and I wanted to actually see how to formalise and reason on. We have 10 players and two courts in our badminton matches. We define a shift to be an instance of ...
Ramit's user avatar
  • 125
0 votes
0 answers
29 views

Prove that in a connected planar graph $G$ with $n \geq 6$ vertices, for any three vertices $u, v, w$, we have $d(u) + d(v) + d(w) \leq 2n + 2$. [duplicate]

Prove that in a connected planar graph $G$ with $n \geq 6$ vertices, for any three vertices $u, v, w$, we have $d(u) + d(v) + d(w) \leq 2n + 2$. This question seems to make use of Euler's formula and ...
Haonan  Li's user avatar
0 votes
0 answers
16 views

Contrapositive to upper bound on number of maximal cliques in $N_{t+1}$-free graphs

This is essentially a follow-up to this question. I realized I was asking the wrong question for what I wanted to know. Background For a positive integer $t$, let $N_t$ denote the cocktail party graph ...
pyridoxal_trigeminus's user avatar
-2 votes
0 answers
39 views

How to navigate on a $27$-grid $3\times 3\times 3$ cube? [closed]

Given that a cube like a Rubik's cube is 27 blocks: How many paths are there which will get you from the middle block to every other block without moving to any block more than once? There can be ...
Lance's user avatar
  • 3,694
1 vote
0 answers
39 views

Polynomial Kernel For Minimum Maximal Matching Problem

Let $G$ be a graph, and $k$ be some non-negative integer. The goal is to decide whether there exists a maximal matching in $G$ on at most $k$ edges. This problem is also asked in https://www.mimuw.edu....
Yavuz Bozkurt's user avatar
0 votes
2 answers
95 views

Betweenness problem algorithm counter-example round 2

I asked in previous question about algorithm proof or counter-example. Alex kindly provided a counter-example, I took my time studying it and why it failed producing a valid ordering, so I came with ...
Ahmad's user avatar
  • 892
1 vote
1 answer
73 views

Percolative process distribution not equivalent to coupon collector problem distribution

I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...
Cardstdani's user avatar
1 vote
1 answer
32 views

$2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$ algorithm to break graphs $\mathcal{F}$ in $G$ with vertex deletion.

Let $G$ be any graph. Let $\mathcal{F}$ denote a set of graphs. We say that $G$ is $\mathcal{F}$ free if none of its subgraphs is isomorphic to a graph $f \in \mathcal{F}$. The problem is to delete at ...
Yavuz Bozkurt's user avatar
0 votes
1 answer
59 views

Island Traveling question

In a faraway ocean, there is a country consisting of many islands. A person can travel from one island to another only by airplane. Fortunately, all airplane routes operate in both directions. The ...
Mike's user avatar
  • 3
-1 votes
0 answers
25 views

Dependence of number of isomorphic copies of a graph on the number of edges

Suppose $H$ is a connected undirected proper subgraph of $K_n$ and $e$ be an edge of $K_n$ incident at one of the vertices of $H$, but not in $E(H)$. Let, for any subgraph $G$ of $K_n$, $M_G$ be the ...
Rathindra N. Karmakar's user avatar
1 vote
0 answers
31 views

Sharp thresholds in bipartite graphs

I have this problem: A random bipartite graph $G(n, n, p)$ is constructed by taking two sets of nodes $L, R$, each of size $n$. For any $u \in L$ and $v \in R$, the probability that the edge $(u, v)$ ...
Nico Konrad's user avatar
1 vote
1 answer
27 views

Correct Counting of Independent Sets in a Complete Bipartite Graph $(K_{n, m})$

I'm diving into graph theory and am currently focused on understanding independent sets within complete bipartite graphs. Specifically, I've been pondering over how to accurately count the total ...
neo's user avatar
  • 109
0 votes
0 answers
53 views

Prove: Let $\{k_{1}, k_{2}, \dots ,k_{j}\}$ be a list of positive integers that sum to $ n $ (i.e., $ \sum_{i=1}^j k_i = n $ [duplicate]

Let $\{k_{1}, k_{2}, \dots, k_{j}\}$ be a list of positive integers that sum to $ n $ (i.e., $ \sum_{i=1}^j k_i = n $ . I am trying to prove the following inequality: $$ \sum_{i=1}^j \binom{k_i}{2} \...
Glo's user avatar
  • 69
1 vote
1 answer
27 views

Prove G has a vertex of a degree 1, if G is a connected graph with n > 1 vertices and n - 1 edges.

Prove $G$ has a vertex of a degree $1$, if $G$ is a connected graph with $n > 1$ vertices and $n - 1$ edges. It says to use the handshake lemma as a hint. and says what would happen if all the ...
Glo's user avatar
  • 69
2 votes
2 answers
262 views

Is Johnson Graph J(N, 2) circulant?

I have stumbled upon the problem of diagonalizing the matrix of a Johnson graph $(N,k)$ with $k=2$. From Wikipedia and several other references I found the explicit form for the eigenvalues https://en....
Alessio Catanzaro's user avatar

1
2 3 4 5
478