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

1
vote
2answers
2k views

Graph theory: If a graph contains a closed walk of odd length, then it contains a cycle of odd length

I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length. Here ...
0
votes
1answer
43 views

Graph theorem(homework) [duplicate]

This is the theorem If $G$ is a graph, there are at least $2$ vertices(points ) always have the same degree. e.g: I have graph $G$, $(U,V)$ ,$4$ vertices $(e1,e2,e3,e4)$ ,and $4$ edges. So the ...
0
votes
1answer
31 views

Necessary and sufficient condition for a set of graphs to be hereditary

Let $\Gamma$ be the set all non-directed loopless graphs without multiple edges. A set $X$ of graphs is called hereditary if each induced subgraph of a graph in $X$ also belongs to $X$. If $M\...
0
votes
2answers
143 views

T and F on some discrete math concepts

I was studying and these questions came up on a review guide on the inter webs, but could was wondering if I was correct on them. 1.Let $B$ $\subset$ $A$ and $f$ : $B$ $\subset$ $A$ be a 1-1 and ...
1
vote
1answer
50 views

Number of edges in a digraph?

I know this might be similar to this question, but I would like to know what the maximum number of edges in a digraph would be if parallel edges (aka multi-edges) are not allowed. I know that the ...
3
votes
1answer
91 views

existence of spanning trees in complete graphs implies choice?

it is known that the existence of spanning trees in arbitrary (connected) graphs implies the Axiom of Choice. I was wondering if this result still holds if we restrict ourselves to spanning trees of ...
1
vote
1answer
81 views

If a graph contains $3$ blocks and $k$ cut vertices, what are the possible values of $k$?

Since blocks can intersect in at most one articulation point, There are from 0 to 3 cut vertices. This is what I have so far. I'm not sure if I need to expand on this or if it is enough of an ...
1
vote
0answers
89 views

A question regarding a prefix code

Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of ...
2
votes
1answer
50 views

Prove that if $G$ is a graph of order $n \geq 3$ such that $deg$ $v \geq \frac{n}{2}$ for every vertex $v$ of $G$, then $G$ is nonseparable

I know a nonseparable graph is a connected graph with simply no cut vertices. And that a graph of order at least $3$ is nonseperable if and only if every two vertices lie on a common cycle. I'm not ...
3
votes
2answers
121 views

What is the average pathlength and probability to cross any given graph?

To get specific first off, it's about this graph: I want to get from $A$ to $B$. Every edge has the same length (e. g. 1 m). The shortest walk from $A$ to $B$ is easily found ($A-2-5-B$ and $A-3-6-...
4
votes
2answers
920 views

Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?

After being given the following two graphs with the same number of edges, vertices and degree, I'm trying to show that they are not isomorphic. At least they seem to be non-isomorphic from the time I ...
1
vote
1answer
53 views

Graphs: Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color.

Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color. My work so far: We know that for each vertex, $v_i$, it's degree is $d(v_i)=16$, because the ...
1
vote
1answer
90 views

Question on Planar Graph

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE? $i)$ In any planar embedding, the number of ...
2
votes
2answers
214 views

Proving a cut vertex in a tree, $T$, is an end-vertex:

If $T$ is a tree of order at least $3$, then $T$ contains a cut vertex $v$ such that every vertex adjacent to $v$, with at most one exception is an end vertex. I know that if $T$ is a connected graph ...
1
vote
1answer
193 views

Do subgraphs imply non-planarity if they correspond to subdivisions of K3,2 and K5 graphs?

I was given this problem: "Determine which of the graphs in figure 2 are planar. In each case either draw a planar graph or exhibit a subgraph which is a subdivision of K3,3 or K5". I did the first ...
3
votes
0answers
48 views

A stronger condition than planar graph?

Is there a name for this condition on a graph: a graph that can be embedded in the plane (planar), in such a way that of its univalent vertices do not lie inside any face? So, one can think of this ...
2
votes
1answer
78 views

The rational unit distance graph is bipartite

I am trying questions from a Graph theory book by Bondy and Murty. I stumbled across a neat looking problem. The unit distance graph on a subset $V$ of $\mathbb{R}^2$ is the graph with vertex set $...
0
votes
1answer
47 views

psittacism: Fundamental Theory of Time

This question is in reference to the programming question found here. What method of approach should I be thinking of if I have a list of lectures A, B, and C, and discussions D, E, and F, that are ...
1
vote
1answer
191 views

Find subgraphs in a directed graph which are isolated by edge properties

Please excuse my small knowledge of graph theory vocabulary. I can only describe the problem with common english words. Maybe someone can point me into the right direction and/or terms to look up. ...
1
vote
1answer
291 views

Hypercubes and bipartite graphs not isomorphic to subgraph of k-cube

Is hypercube and k-cube the same? I did see the question in another post here, but I am not able to comment there since I do not have much reputation, and I am not allowed to post a doubt as answer. I ...
1
vote
0answers
26 views

Genus of a simple graph $G$.

Let $G$ be a simple graph with set of vertices $V(G)=\{a_i,v_j \mid 1\leq i \leq 5, 1\leq j \leq 4\}$ and the set of edges is $E(G)=\{a_ra_s,v_1v_2,v_1v_3,v_1v_4,v_1a_1,v_1a_2,v_1a_3,v_2a_1,v_2a_4,...
6
votes
2answers
3k views

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$. How would I show this? I understand that a cycle is a sequence of non-repeated vertices and the ...
2
votes
4answers
3k views

Prove that if there is a walk from u to v then there is also a path from u to v.

Let G be a graph and let u and v be two of its vertices. Prove that if there is a walk from u to v then there is also a path from u to v. Using induction on length of a path, how can I solve this? ...
0
votes
1answer
78 views

Explicit expression of eigenvalue and eigenvector of a graph

Could any one tell me what kind of graph has the explicit expression of its eigenvalue and eigenvector? Thanks!
2
votes
1answer
49 views

When is a linegraph Eulerian?

So I know that for a simple Eulerian graph, its linegraph is also Eulerian. (Since then, each degree of the nodes of the linegraph are also even). I'm asked to give (sufficing) conditions for a graph $...
8
votes
2answers
180 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: http://www.chiark.greenend....
1
vote
1answer
32 views

Restrict edge set to certain nodes only

Given a graph $G=(V,E \subseteq V \times V)$, an edge set $D \subseteq E$ and a subset of nodes $W \subseteq V$, is there such thing as an established operator for the "restricted" set of $D$: $$ \{ (...
0
votes
1answer
77 views

Number of labelled graphs.

I'm still beginner in mathematic. How to prove this formula with induction or another way. I have: $2^{ n(n-1) /2}$, if , i sum this i have $1+2+8+64+...$ so on. How i can prove its equal to ...
0
votes
1answer
44 views

Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
1
vote
0answers
125 views

Proof of Gallai's Theorem for Critical Graphs

A fundamental theorem in Graph theory is the following: Let $G$ be a $k$-critical graph with $k\geq 4$ and $G\neq K_k$. Then every block in the subgraph of $G$ induced by the vertices of degree $k-1$ ...
3
votes
1answer
286 views

Number of edges in graphs having two disjoint cycles of equal length

The question is motivated by this and this two problems. The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the ...
-1
votes
1answer
52 views

Proving that a bipartite graph, of minimum degree $4$, doesn't contain $K_{3,3}$

Prove that a bipartite graph, of minimum degree $4$, doesn't necessarily contain $K_{3,3}$ I know I just need a counter example, but I'm having some extreme difficulty finding one.
2
votes
0answers
62 views

A random walk on the unit distance graph in $\mathbb{R}^n$

Define a graph $G_n$ whose vertices are the points in $\mathbb{R}^n$ with an edge connecting any two points that are one unit apart. Such a graph is called the unit distance graph in $\mathbb{R}^n$. ...
4
votes
2answers
671 views

Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove >that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42) I am trying to prove the ...
1
vote
2answers
110 views

On the graph of induction-restriction for group-subgroup representations

Let $G$ be a finite group, and $H$ a subgroup. Let $(V_i)_{i \in I}$ and $(W_j)_{j \in J}$ be the irreducible complex representations of $G$ and $H$ (up to isom.). Consider the graph $\mathcal{G}(...
0
votes
2answers
65 views

Given 4 persons, how many possibilities that in each triplet there will be both friends and strangers?

I am asking for tips to following question: Given 4 persons, how many possibilities that in each triplet there will be both friends and strangers? I've tried to count drawing all possibilities, for ...
2
votes
1answer
224 views

Why isn't the Four Color Theorem be proven by Kuratowski's theorem?

We know that the graphs $K_5$ and $K_{3,3}$ are not planar. The complete graph $K_5$ means that all 5 vertices are adjacent, thus requiring 5 different colors to allow coloring without two adjacent ...
5
votes
1answer
84 views

Infinite sequence of trees that are not subgraphs to each other

This is from a set of exercises and I am stuck to this. Please, have in mind, that I want to understand how it's solved, I am not just looking for a solution. Define an infinite sequence of trees $...
1
vote
1answer
90 views

If $n \geq 6$, $G$ or $G_c$ contains a cycle of length $3$

That is the statement, if the order of $G$ is greater or equal to $6$, $G$ or its complementary contain a cycle of length $3$. I don't really know where to start, I have drawn a lot of examples but ...
3
votes
1answer
240 views

How to prove that for any graph on $8$ nodes with exactly $17$ edges has at least $4$ triangles.

Question: for any graph on $8$ nodes with exactly $17$ edges has at least $4$ triangles. for example, This picture at least 4 triangles from this : I found this reslut: for any graph on $2n+\...
3
votes
0answers
30 views

How do I find the lowest $k$ for which a graph is $k$-partite?

An undirected graph is bipartite if its vertices can divided into two non-empty sets for which no two vertices in the same set have an edge with each other. We can test if a graph is bipartite by ...
0
votes
1answer
170 views

Graph Coloring Question

Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.) It is easily know that star-graphs are ...
2
votes
1answer
96 views

References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph $...
2
votes
2answers
131 views

Text on Group Theory and Graphs

A student and I are going to investigate the use of group theoretic techniques in graph theory. What are good texts in this area (introductory and otherwise)? We are particularly interested in ...
0
votes
1answer
66 views

Graphic sequence and connectivity

The question is as follows: Given the graphic sequence d=$\langle d_1,d_2,...,d_n\rangle$. Assuming $d_i\ge2$ for every i. Show that a simple and connected graph with such graphic sequence exists. ...
3
votes
2answers
382 views

Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$

Prove that the maximum connected components in a graph is $V+1-\left\lceil\frac{1+\sqrt{1+8E}}{2}\right\rceil$ I came up with this intuitively but was not able to prove it. The idea is that a graph ...
1
vote
1answer
104 views

What is dist[i][i] in Floyd–Warshall

So in the Floyd–Warshall algorithm, it will calculate all shortest paths in a weighted graph with positive or negative edge weights. I know that dist[i][j] is the closest distance from i to j node. ...
1
vote
1answer
58 views

For which values of n does G have an eulerian trail

The question is as follows: Let $n\ge3$ be a natural number. Let $G=(V,E)$ where $V=\{1,2,3,\dotsc,2n\}$ and $E=\{\{i,j\}:|i-j| \in \{3,5\}\}$. Prove that $G$ is bipartite. For which ...
0
votes
1answer
104 views

How to know if a node is surrounded?

I'm an IT student working on a school project. We are building a game where 2 players can fight over and colonize planets. A specific game mechanic is that if a player creates a perimeter of planets, ...
2
votes
2answers
101 views

Given a walk in a graph, find a path and an odd cycle contained in the trail.

Given this graph: And given the $1-8$ walk $$C_1=(1,3,2,3,4,5,3,6,7,6,8),$$ find a $1-8$ path. Note: trails do not repeat edges, paths do not repeat vertices. Lastly, given this closed odd-length ...