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.

23,894 questions
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 ...
• 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 ...
• 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$ ...
• 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 ...
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?
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 ...
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 ...
• 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$ ...
• 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 ...
• 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 ...
• 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?) ...
• 33
1 vote
1 answer
38 views

• 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 ...
• 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....