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.

learn more… | top users | synonyms

0
votes
1answer
21 views

vertex cover of size k in a degree two vertices graph

Let $G=(V,E)$ be a simple graph where $\forall \ v\in V:\ degree(v)=2$. Consider the question: "Is there a vertex cover for $G$ like that of size k?" My approach Because $\sum_{v\in V}degree(v)...
3
votes
0answers
20 views

Cardinality of Set of Rooted Spanning Trees of Integer Lattice

I am wondering whether there are countably many or uncountably many spanning trees of the integer lattice rooted at a particular vertex, say the origin. In a spanning tree rooted at the origin there ...
0
votes
0answers
27 views

how to find the angle of Lovasz umbrella

in the book Thirty-three Miniatures: Mathematical and Algorithmic Applications of in problem 28 The Secret Agent and the Umbrella page 132 (pdf 140) we want to find an orthogonal reperesentation of ...
0
votes
0answers
124 views

Simple objects to paint in different dimensions

I want to generalize the question How many colors in 3-d space to paint boxes? for cases in different dimensions and to paint simple objects defined in different dimensions. An appropriate subset of "...
0
votes
1answer
13 views

Sufficient condition for directed graph having an even directed cycle.

I want to show that a directed graph $D$ on $n$ vertices with minimum out-degree $(\log_2 n) + 1$ always has an even directed cycle. I first saw this claim here with a version as an exercise here. I'...
1
vote
0answers
14 views

Minimal cut set and spanning tree

Let be $G$ a graph. Show that if $A$ is a minimal subset of edges by contention and contains exactly one edge from every spanning tree of $G$, then $A$ is a minimum subset of $G$. I try to give a ...
3
votes
1answer
19 views

Let be $G$ a graph of order $n$. Show that if $\delta(G) = \frac{n}{2}$, then $\lambda(G) = \delta(G)$

I was reading the book graph theory by harary, and he prove the upper bound for the edge connectivity, and mentions that the equality holds when $\delta(G) = \frac{n}{2}$, Any ideas how to prove it.
0
votes
1answer
22 views

Is this the correct directed graph for this relation?

The relations is defined by the set of ordered pairs $$R = \{(1,2),(1,3),(2,3),(3,4),(3,1),(3,2),(3,3),(4,4)\}.$$ Please excuse my drawing, I'm very sorry for it, I hope it's understandable though.
0
votes
1answer
23 views

Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
2
votes
1answer
88 views

Coloring a Complete Graph in Three Colors, Proving that there is a Complete Subgraph

Color the edges of a complete graph on $n$ vertices $K_n$ in three colors (red,blue,yellow) such that at most $\dfrac{n^2}{k}$ are colored red ($k$ is some natural number). Prove that $K_n$ ...
1
vote
2answers
13 views

Max Flow Minimum Cut - after removing an edge

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut. Why is it must be that the max flow after removing $e$ is exactly $|...
1
vote
0answers
28 views

A graph $G$ is $r$-factorable iff $G$ is $k$-regular and $k$ is a multiple of $r$

An $r$-factor of a graph like $G$ is a spanning subgraph of $G$ which is $r$-regular. A graph $G$ is called $r$-factorable if we can decompose edges of $G$ to $r-$factors. Prove that : A graph ...
7
votes
1answer
138 views

How many colors in 3-d space to paint boxes?

Let's imagine that we have boxes shaped as rectangular cuboids and colored with many different colors (one color for one box). Boxes can touch themselves by faces. Their edges are parallel to axes $\...
0
votes
1answer
19 views

How many minimum spanning tree of following graph is possible.

How many minimum spanning tree of following graph is possible. My attempt: I've tried it manually as : Therefore, Total possible number of minimum spanning trees are $=2\times2\times2+...
0
votes
0answers
19 views

Which of the following cannot find for disconnected graph of n vertex.

Which of the following cannot find for disconnected graph of n vertex. Matching number of graph Covering number of graph Independent set number of graph All My attempt: Matching number: Given ...
0
votes
0answers
28 views

Graph with odd number of common neigbors

can you check my soultion? Task:In graph G every two vertices have odd number of common neighbors. Prove that every vertex has even degree. My thinking. I choose arbitrary vertex $v$ and build ...
1
vote
1answer
20 views

Chromatic number of a graph after a vertex is deleted from it.

What happens to the chromatic number of a graph, G, when one of its vertices, v, is deleted? By this I mean what will be the chromatic number of the subgraph G-v? I know that the chromatic number can ...
2
votes
0answers
31 views

Automorphism and Direct Product of Generating Set

Notation: $H $ are partitioned into sub-graphs $ H_1,H_2 \cdots H_x$ . We see them in the adjacency matrix of $H$ given below- $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-...
6
votes
2answers
111 views

How many different isomers of $C_3 H_4 Cl_2 F_2$ exist?

I was on my high school chemistry class when I came across this problem, which, I think, belongs to group theory. The problem is that it is not possible to label the carbons as reflection should not ...
0
votes
0answers
12 views

what is the time complexity of checking the conservation of flow in a network?

As you may know, considering a network with the set of nodes $V$, the conservation of flow law is the followings: $$\sum_{v \in V} f(u, v) = 0, \quad \text{for all $u \in V \setminus \{s,t\}$}$$ and ...
1
vote
0answers
46 views

Proving that a random graph is almost surely connected

So, I'm trying to show that a random graph is almost surely connected. I want to know if my intuition is correct, and if so, how to formalize that intuition into a proof. If a graph $G=(V,E)$ has $|V|...
0
votes
1answer
35 views

Four color theorem and five color theorem

Every graph whose chromatic number is more than ____ is not planner. My attempt: The answer should be $4$ by four color theorem. Somewhere, I read "Five color theorem"(See Theorem 6.3.8 at ...
0
votes
0answers
22 views

Finding highest sum with limited cost using variable Nodes

I am practical guy(programmer) and I've been trying to solve this problem by "brute force" and of course this solution isn't really fast. Problem: There is a static graph (11 nodes) where each node ...
0
votes
1answer
33 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
1
vote
1answer
29 views

A graph whose vertices all have degree $2$ must contain a cycle

I've been working on some beginner graph theory, and I was having some funky issues with this particular problem. Consider a graph $G$ such that for all $x \in V(G),\, \deg(x) = 2.$ I want to prove ...
1
vote
1answer
32 views

In a maximal planar graph, are two consecutive neighbors of a vertex necessarily adjacent?

If we pick a vertex $v$ and two consecutive neighbors of it, $u_1$ and $u_2$, are we sure that $(u_i, u_{i+1}) \in E$? Note: by consecutive I mean in a planar embedding; otherwise any two neighbors ...
0
votes
1answer
37 views

prove that the minimum number of trails in an odd graph is n/2

In my HW assignments I was asked to prove that If a graph G consists of only odd degree vertices, then the minimum number of trails that decompose it (without having any common edge between each two ...
1
vote
0answers
19 views

An extemal combinatorial design question. “Weak” steiner stystems.

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly $...
0
votes
0answers
18 views

Prove if $G$ and $H$ are graphs on the same vertex set, then $dg(G∪H)≤dg(G)+dg(H)$

Prove if $G$ and $H$ are graphs on the same vertex set, then $dg(G∪H)≤dg(G)+dg(H)$ $dg(G)$ is the the minimum k such that $G$ is k-degenerate. I know it can be proved with respect to graph coloring, ...
0
votes
2answers
33 views

Polyhedron with 12 pentagons and 1 hexagon

In this answer http://mathoverflow.net/a/19823/5239, it is indicated that it is impossible to make a polyhedron (with 3 faces meeting at each vertex) out of 12 pentagons and 1 hexagon. There is ...
0
votes
1answer
31 views

How to find the eigen values

How to find the eigen values of the graph having vertex set as $\{1,2,.......n\}$ and edge set as $\{(l,l+1)\}$ $ \cup (1,n)$ ? where $1\le l \le n$. Here I am considering the Laplacian matrix of ...
6
votes
3answers
104 views

Quotient of a graph?

I want to understand quotient of a graph (also called quotient graph), my teacher says that the terms quotient of a graph and a modulo of a graph should be synonyms (even though modulo of a graph ...
1
vote
0answers
21 views

Quasi-Group represented by a graph which is not a Triangle-Free Graph locally

Can each of all quasi-groups be represented by a graph (latin square graph), which is not locally triangle free graph ? Quasi Group can be represented by Latin Square matrix, thus by a Latin ...
0
votes
0answers
13 views

Network with more than one maximum s-t flow

I'm struggling to think of an example of a network with more than one maximum s-t flow. In addition, is there an efficient way to identify whether or not a network has a unique maximum s-t flow?
0
votes
0answers
31 views

How to count all cycles (simple or not) in a directed complete graph?

I came up with an algorithm for counting cycles (simple or not) of length less or equal to n in a given directed complete graph Kn. I am looking for a more concise way of counting cycles but have not ...
1
vote
0answers
20 views

HM question- the graph K4,3

We've been asked to prove the following: Prove that you can place K4,3 on the plane with exactly two intersects. then, prove that you can't do it with less intersections. someone?
0
votes
0answers
10 views

Neighborhood structure in a uniform hypergraph

Consider a $k$-uniform connected hypergraph with vertex set $V$ and hyperedge set $E$, as defined in https://en.wikipedia.org/wiki/Hypergraph#Symmetric_hypergraphs . We impose the following condition ...
1
vote
3answers
31 views

proof about hall's theorem in graph theory

Prove that a k regular bipartite graph has a perfect matching by using hall's theorem. Approach Let S be any subset of the left side of the graph The only thing I know is the number of things ...
0
votes
0answers
33 views

Why must every bridge in an Eulerian walk/circuit be traversed twice? (Chinese Postman Problem)

Does it have to do with the degrees of the vertices? The book I was reading has this as a theorem but doesn't include the proof for some reason. This was in the context of the Chinese Postman Problem. ...
1
vote
2answers
49 views

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected graph?

What's the most efficient algorithm to check the number of cycles of length 4 in an undirected, unweighted graph?
1
vote
0answers
28 views

What is an algorithm for finding the shortest path in a graph that crosses each edge at least once.

I am looking for an algorithm that, given a graph, finds the shortest (or approximately shortest) path that crosses all edges at least onces. (Multiple times crossing an edge is allowed!) The graph ...
1
vote
1answer
22 views

Euler formula. 100 faces

can you give any clue to this task: I have polyhedron with 100 faces, in which 50 are triangles and 50 rectangles. Prove that at least one of vertices has degree $\ge 5$.
1
vote
0answers
23 views

Number of Vertices with $\mu$ Common Neighbor

$\mathcal{G}$ is a graph class. Each graph $G$ of $\mathcal{G}$ has the following properties- $G$ is a $k$ (variable with respect to different graphs) regular graph of $n$ vertices. The vertex set $...
1
vote
0answers
19 views

Derive Hall's theorem from Tutte's theorem

I'm trying to derive: Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$ From this: Tutte Theorem A graph G has a 1-...
0
votes
0answers
16 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
1
vote
1answer
16 views

Duality theorem between Cycle Space and Cut Space in terms of Matrices?

The book Graphs and Matrices by Bapat formulates linear algebra on graph theory, yet I cannot find important theorems such as Duality theorem between the cycle space and the cut space (Diestel p.26, ...
1
vote
1answer
41 views

Graph with exactly one perfect matching

How do I prove that if $ G $ graph, with $2n$ vertices, has exactly one perfect matching then $ |E(G)| \le n^2 $ ?
2
votes
2answers
41 views

The existence of a cycle in a graph

Let $C$ and $D$ be different cycles in the graph $G$, and $e$ a common edge of cycles $C$ and $D$. Show that $G$ contains a cycle not passing through the $e$. I think, it's not easy task, because ...
0
votes
0answers
14 views

$k$-regular connected graph with no perfect matching

How do I construct a $k$-regular connected graph with no perfect matching? I know that if $G$ is $k$-regular bipartite graph it has perfect matching, so the graph that I'm looking for shouldn't be ...
0
votes
0answers
41 views

Propositional formulas for connected graph

I have some difficulties with the following problem. Let $G = (V,E)$ be a graph with $V = \mathbb N$ (natural numbers) and $E \subset \mathbb N^2$. Let $p_{ij}$ be a set of propositional ...